Grizzly's daily
0%

单链表解题技巧(2)——快慢指针

发表于 更新于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟

本文是关于单链表的双指针问题中的快慢指针问题，1.链表的倒数第 n 个结点；2.寻找链表中间结点；3. 判断是否有环。

涉及 leetcode 的 19. 删除链表的倒数第 N 个结点、876. 链表的中间结点、141. 环形链表和142. 环形链表 II。

倒数第 N 个结点

题目1

首先来看题目19. 删除链表的倒数第 N 个结点：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例1：

输入：head = [1,2,3,4,5], n = 2

输出：[1,2,3,5]

示例2：

输入：head = [1], n = 1

输出：[]

理解一下1

不用理解！(狗头)

基本的思路是：

  1. 先遍历一遍链表，得到链表的长度Len；
  2. 然后再从头遍历一遍到第Len-N个结点，该结点的后一个结点就是需要删除的结点。

以上的思路确实可以解决该问题，但是对链表进行了两次遍历，那么是否可以使用一次遍历完成呢？可以的。

这就需要使用快慢指针了：

  1. 我们需要找到倒数N个结点，那么就需要寻找到第Len-N个结点；
  2. 首先让快指针先走，走出N步；
  3. 然后让慢指针和快指针保持相距N一起向前遍历，这时快指针还有Len-N步到达链尾，那么慢指针自然就还可以走Len-N步啦！

解题1

这里我们同样需要对第一个结点进行讨论，所以直接引入头结点来解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* removeNthFromEnd(ListNode* head, int n) {
    //使用头结点
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    // 快慢结点
    ListNode *first = dummy, *second = dummy;
    // first先走n步
    for(int i = 0; i < n; i++){
        first = first->next;
    }
    // first和second保持相同的间距前进
    // first指向终点时second指向将要删除结点的前一个
    while(first->next != nullptr){
        first = first->next;
        second = second->next;
    }
    // 删除（未释放空间）
    second->next = second->next->next;
    return dummy->next;
}

中间结点

再来看一下中间结点的问题，其实是相同的套路。

题目2

先来看一下题目876. 链表的中间结点：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

示例1：

输入：[1,2,3,4,5]

输出：此列表中的结点 3

示例2：

输入：[1,2,3,4,5,6]

输出：此列表中的结点 4

理解一下2

也不用理解！(狗头)

基本思路与上一题类似：

  1. 先遍历一遍链表，得到链表的长度Len；
  2. 然后再从头遍历一遍到第Len/2个结点即可。

这同样需要使用两次遍历，有了上面的经验我们自然可以想到使用快慢指针实现一次遍历：

  1. 快指针和慢指针同时出发（与之前先后出发不同了）；
  2. 快指针一次走两个next，慢指针一次进行一次next，这样快指针走到最后，慢指针刚好走了快指针的一般路程。

题解2

这里根据题目要求注意一下中间结点的定义即可。

[]
1
2
3
4
5
6
7
8
9
ListNode* middleNode(ListNode* head) {
    ListNode * first = head, * second = head;
    while(first != nullptr && first->next != nullptr){
        // 慢指针走一步，快指针走两步
        second = second->next;
        first = first->next->next;
    }
    return second;
}

同样套路，还有一个啦（二合一）

环形链表

题目3

141. 环形链表和142. 环形链表 II这两题类似。

141 给你一个链表的头节点 head ，判断链表中是否有环。

以及

142 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

理解一下3

也就是说需要判断链表是否有环，以及从哪个结点开始形成环。

那么我们首先需要知道如何判断环：

  1. 容易发现，一旦使用指针在有环链表中进行遍历，那么遍历一定是没有终止；就像操场跑步一样，只要沿着400米的圈一直跑就没有尽头，但是沿着100米的直线跑却是有尽头的；
  2. 同样的，当我与你一起在100 + 400n米的操场上跑步，从我跑得慢，你跑得快，那么你是不是终究就会在某个点上超过我一圈！
  3. 因此我们同样可以使用快慢指针进行你追我赶，当然，补偿为1、2、3这种连续遍历，可能会超过K圈（整数倍），不过无所谓，你我终会相遇。

然后如何判断在哪相遇呢？（你的速度是我的两倍）

  1. 慢吞吞的我跑了n米，快吨吨的你跑了2n米，相遇时距离环起点也m米；
  2. 那么超过我的距离n一定是环的整数倍，所以你再跑n-m米就可以到达环起点，而我回到起点再跑n-m米也能到达环起点！
  3. 这里就不需要计数n了，保持相同速度跑，自然会在起点相遇，你我终会再次相遇。

题解3

判断方法如下：

[]
1
2
3
4
5
6
7
8
9
10
11
12
bool hasCycle(ListNode *head) {
    ListNode *first = head, *second = head;
    // 同样使用快慢指针，若存在环，那么快指针将会在环内与慢指针相遇
    while(first != nullptr && first->next != nullptr){
        first = first->next->next;
        second = second->next;
        if(first == second){
            return true;
        }
    }
    return false;
}

寻找环起点的方法如下：

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ListNode *detectCycle(ListNode *head) {
    ListNode *first = head, *second = head;
    // 标记是否相遇
    bool flag = false;
    while(first != nullptr && first->next != nullptr){
        first = first->next->next;
        second = second->next;
        if(second == first){
            flag = true;
            break;
        }
    }
    if(flag){
        // 任意一个结点回到起点，同样速度跑
        first = head;
        while(first != second){
            first = first->next;
            second = second->next;
        }
        return second;
    }
    return nullptr;
}

个人收获

这次的收获主要是头结点和快慢指针

  1. 头结点使得每个结点都有直接前驱，可以避免单独处理第一个结点的问题，很好用的；
  2. 快慢指针可以用来解决一些与速度、距离有关的问题会有较好的处理方法，在后续的题目中多熟悉熟悉。
------ 本文结束------