Leetcode:链表中快慢指针的使用场景
文章目录
(持续补充中)
一、寻找某个节点
1、返回倒数第k个节点
这个可以用一般的思维模式去处理,也就是先遍历一遍确定链表长度,例如以下处理方式:
也可以使用快慢指针:
思路如下:
寻找倒数第k个节点,是一个找链表上的某个节点的问题了,这是快慢指针最擅长的场景。
那如何找第k个元素呢?我们一开始就让fast指针比slow指针快k个元素,接下来,两个指针都是一步一步来往下走。那么当fast指针走完时,slow指针就刚刚好停留在第k个元素上。
这是因为两个指针始终相距k个节点,所以当快节点指向最后时,慢节点刚好指到倒数第k个节点。
(如果是删除第k个节点的话,就相当于寻找第k-1个节点)
注意:
看清楚要返回的是倒数第k个值,还是倒数第k个链表。
例如:
所以最后不能返回a.val,而应该返回 a