链表-02

双指针技巧

我们之前在数组中引入了双指针技巧，先做一个简要回顾，有两种使用双指针的情景：

两个指针从不同位置出发：一个从头部开始，另一个从尾部开始；
两个指针以不同速度移动：一个指针快一些，另一个指针慢一些；

对于单链表，由于我们只能在一个方向上遍历链表，所以第一种情景可能无法工作。但是第二种指针，即快慢指针是非常有用的技巧。

以下我们将重点讨论链表中的快慢指针问题，并告诉你如何解决这类问题。

链表中的双指针

首先从一个经典问题开始：

给定一个链表，判断链表中是否有环。

熟悉哈希表的可能已经使用哈希表提出了解决方案。但是，使用双指针技巧有一个更有效的解决方案。

想象一下，有两个速度不同的跑步者。如果他们在直路上行驶，快跑者将首先到达目的地。但是，如果它们在圆形跑道上跑步，那么快跑者如果继续跑步就会追上慢跑者。

这正是在链表中使用两个速度不同的指针时会遇到的情况：

如果没环，快指针将优先抵达链表尾部。
如果有环，快指针最终将会追上慢指针。

所以剩下的问题是：这两个指针的适当速度应该是多少？

一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。

我们用题目来展现问题：

题目：环形链表

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果 pos 是 -1，则在该链表中没有环。

示例：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

进阶：使用 O(1) 内存解决此问题，即空间复杂度为O(1)

个人理解：
采用刚了解到的快慢指针法来判断链表中是否有环即可。
定义快慢指针，让快指针一次走两部，慢指针一次走一步：如果快指针抵达终点，说明链表内部没有环；如果快指针追上了慢指针，则说明链表内部有环存在。

代码如下(C++):

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast{head}, *slow{head};  // 定义双指针
        if(head == nullptr) return false;   // 特判
        while(fast != nullptr && fast -> next != nullptr){  // 判断是否到头
            fast = fast -> next -> next;    // 走两步
            slow = slow -> next;            // 走一步
            if(fast == slow) return true;   // 相遇则为环
        }
        return false;                       // 否则到尽头无环
    }
};

题目：环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

个人理解：
查看示例的内容我们可以得知，这次要返回的是环的点，所以我们还是采用双指针法来解决。
官方称之为：Floyd 算法，如果链表中有环存在，快指针必然会追上慢指针，在此我们设定，起点为 A，环点为 B，追逐点为 C，令：
A->B 为 x
B->C 为 y
C->B 为 z
慢指针走的路线为：x + y
快指针走的路线为：x + y + z + y
又因：快指针 = 慢指针 * 2
可得：x = z
即我们想要的 B 点，其实就是 x 的长度，所以在相遇后，将慢指针放回起点，两个指针继续走，再次相遇就是 B 点相遇了。

代码如下(C++):

class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    ListNode *fast{head}, *slow{head};    // 定义双指针
    if(head == nullptr) return nullptr;   // 特判
    while(fast != nullptr && fast -> next != nullptr){  // 判断是否到头
      fast = fast -> next -> next;        // 走两步
      slow = slow -> next;                // 走一步
      if(fast == slow){           // 相遇则为环
        slow = head;
        while(fast != slow){      // 将slow放回头部，继续走
          slow = slow -> next;    // 走一步
          fast = fast -> next;    // 走一步
        }
        return slow;              // 相遇返回slow即可
      }
    }
    return nullptr;               // 否则到尽头无环
  }
};

题目：相交链表

编写一个程序，找到两个单链表相交的起始节点。
如下两个链表：

在节点C1开始相交。

示例：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

个人理解：
利用两个链表总路程一样，进行遍历：
分别定义两个指针在两个链表头部，每次走一步，走完自己路程去走另一个链表内容，最终步数均为 x + y
如果相遇则结束，相遇点即为交点，最后也同时抵达结尾 null，最终返回 null。

代码如下(C++):

class Solution {
public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *a{headA}, *b{headB};  // 定义两个指针分别在两个链表头部
    if(headA == nullptr || headB == nullptr)
      return nullptr;               // 都为空则肯定没交点
    while(a != b){                  // 总路程是一样的，都是 a + all + b
      if(a == nullptr)  a = headB;  // a到头交换到B链表头部
        else a = a -> next;         // 走一步
      if(b == nullptr)  b = headA;  // b到头交换到A链表头部
        else b = b -> next;         // 走一步
    }                               // 两个同时到达结尾 null，结束循环，返回null
    return a;
  }
};

题目：删除链表的倒数第 N 个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头节点 1。

示例：

1 2	给定一个链表: 1->2->3->4->5, 和 n = 2 当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：给定的 n 保证是有效的

进阶：尝试使用一趟扫描实现

个人理解：
采用双指针的另一种用法，还是同向移动，但是，一个指针先移动一定的距离，用作距离标定，随后开始步进，另一个指针联动。
做法如下：

先定义一个哑节点放在头部
在哑节点位置定义两个指针
将一个指针先行 n+1 步
一起移动，知道先行指针到头
此时后指针就在要删除节点前
删除节点即可

class Solution {
public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *header = new ListNode(0);   // 定义一个哑节点
    header -> next = head;                // 将哑节点放在头部
    ListNode *a{header},*b{header};       // 在哑节点位置放置两个指针
    for(int i = 0; i < n+1; i++)  b = b -> next;    // 将 b 指针先移动 n+1 步
    while(b){                                       // 将 b 指针移动到头，a 指针联动
      a = a -> next;
      b = b -> next;
    }
    a -> next = a -> next -> next;        // a 这时候位置就在要删除节点前
    return header -> next;                // 返回 header->next 即可
  }
};

小结 - 链表中的双指针

在这里，我们为你提供了一个模版，用于解决链表中的双指针问题。

模版如下(C++):

// 初始化快慢指针
ListNode* slow = head;
ListNode* fast = head;
/**
 * 根据不同的问题更改条件
 * 注意: 记得避免空指针错误
 **/
while (slow && fast && fast->next) {
    slow = slow->next;          // 每次将慢指针移动一步
    fast = fast->next->next;    // 每次将快指针移动两步
    if (slow == fast) {         // 根据不同的问题更改条件
        return true;
    }
}
return false;   // 更改返回值以适合特定问题

提示

它与我们在数组中学到的内容类似。但它可能更棘手而且更容易出错。你应该注意以下几点：

1.在调用 next 字段之前，始终检查节点是否为空：
获取空节点的下一个节点将导致空指针错误。例如，在我们运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。

2.仔细定义循环的结束条件：
运行几个示例，以确保你的结束条件不会导致无限循环。在定义结束条件时，你必须考虑我们的第一点提示。

复杂度分析

空间复杂度分析容易。如果只使用指针，而不使用任何其他额外的空间，那么空间复杂度将是 _O(1)_。但是，时间复杂度的分析比较困难。为了得到答案，我们需要分析运行循环的次数。

在前面的查找循环示例中，假设我们每次移动较快的指针 2 步，每次移动较慢的指针 1 步。

如果没有循环，快指针需要 N/2 次才能到达链表的末尾，其中 N 是链表的长度。
如果存在循环，则快指针需要 M 次才能赶上慢指针，其中 M 是列表中循环的长度。
显然，M <= N 。所以我们将循环运行 N 次。对于每次循环，我们只需要常量级的时间。因此，该算法的时间复杂度总共为 O(N)。

自己分析其他问题以提高分析能力。别忘了考虑不同的条件。如果很难对所有情况进行分析，请考虑最糟糕的情况。

声明：本文为学习记录，不做商业用途，如果有侵权内容，请联系我立即删除。