作者：whisper

链接：http://proprogrammar.com:443/article/246

声明：请尊重原作者的劳动，如需转载请注明出处

    我们在另一张卡片中引入了双指针技巧：数据结构简介 - 数组和字符串.

    让我们简要回顾一下这种技巧。 我们提到了两种使用双指针技巧的情景：

1. 两个指针从不同位置出发：一个从始端开始，另一个从末端开始；
2. 两个指针以不同速度移动：一个指针快一些，另一个指针慢一些。

    对于单链表，因为我们只能在一个方向上遍历链表，所以第一种情景可能无法工作。然而，第二种情景，也被称为慢指针和快指针技巧，是非常有用的。

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

    链表中的双指针

    让我们从一个经典问题开始：

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

    你可能已经使用哈希表提出了解决方案。但是，使用双指针技巧有一个更有效的解决方案。在阅读接下来的内容之前，试着自己仔细考虑一下。

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

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

1. 如果没有环，快指针将停在链表的末尾。
2. 如果有环，快指针最终将与慢指针相遇。

    所以剩下的问题是：

这两个指针的适当速度应该是多少？

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

那其他选择呢？它们有用吗？它们会更高效吗？

    算法说明

    环形链表

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

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

示例 1：

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

示例 2：

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

示例 3：

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

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

// 想法：暴解：将结点放入List中，看是否会出现相等；或放入Set中，看长度是否增加
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        Set<ListNode> sets = new HashSet<>();
        int length = 1;
        while(head != null){
            sets.add(head);
            if(sets.size() != length++){
                return true;
            }
            
            head = head.next;
        }
        
        return false;
    }

    通过将结点放入set中，如果放入后长度不增加说明有环，但不是常量内存，看一下其它的解法

public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null ){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }

    使用了快慢指针，如果存在环的话，可以证明快慢指针一定会相遇，如下图，当慢指针进入环时，快指针已经在环中一个位置(7)，快指针的位置还有几个元素到环入口（此时慢指针在环入口），只要走相隔的元素的步数，快慢指针就会相遇，如下图快指针再有两个元素（8，1）到环入口，那么再循环两次（走两次），那么快慢指针将在3处相遇

    环形链表 II

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

进阶：
你是否可以不用额外空间解决此题？

// 想法：用Set，add后长度不增加则重复了，说明是入口
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        
        Set<ListNode> set = new HashSet<ListNode>();
        int len = 0;
        while(head != null){
            set.add(head);
            if(set.size() != ++len){
                return head;
            }
            
            head = head.next;
        }
        
        return null;
    }

    还是用set，如果长度不增加，说明出现重复了，这个重复的就是环的入口，这里用了o(n)的辅助空间，看一种更好的解法

public ListNode detectCycle(ListNode head) {
        if (head == null)
            return head;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

    这里没有使用额外的空间，这里当第一次相遇时，使慢指针返回head，再次相遇时即是在环入口相遇，这里解释一下，如下图，设当第一次相遇时慢指针走了a个元素，快指针走了b个元素，此时b=2a（因为慢指针走一步快指针走两步），即2(M+N)=M+N+L+N，即L=M，此后慢指针回到head，快指针变得和慢指针同速，当慢指针走M到环入回时，快指针也走了M（即L）也到了环入口，即会在环入口再次相遇。

    相交链表

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

    如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：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 个节点。

示例 2：

输入：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 个节点。

示例 3：

输入：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.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

// 想法：这次用List
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        List<ListNode> listA = new ArrayList<>();
        List<ListNode> listB = new ArrayList<>();
        
        while(headA != null) {
        	listA.add(headA);
        	headA = headA.next;
        }
        
        while(headB != null) {
        	listB.add(headB);
        	headB = headB.next;
        }
        
        ListNode result = null;
        
        for(int i = listA.size() - 1; i >= 0; i--) {
        	if(listB.contains(listA.get(i))) {
        		result = listA.get(i);
        	}else {
        		break;
        	}
        }
        
        return result;
    }

     因为没有环，所以我用了list存储两个相交的链表，并找出其中第一个共同的结点，看一下更好的方法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int size1 = 0;
        int size2 = 0;
        ListNode pointer = headA;
        while (pointer != null) {
            size1++;
            pointer = pointer.next;
        }
        pointer = headB;
        while (pointer != null) {
            size2++;
            pointer = pointer.next;
        }

        int size = Math.abs(size1 - size2);
        if (size1 > size2) {
            for (int i = 0; i < size; i++) {
                headA = headA.next;
            }
        } else {
            for (int i = 0; i < size; i++) {
                headB = headB.next;
            }
        }
        
        while (headA !=null && headB !=null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}

    这里的想法是找到较长链表的后若干个元素，这里的后若干个元素指较短链表长度个元素，这样不相交部分的长度就相同了，此时两个链表每次向后移动一个位置，会同时到达相交的位置

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

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

示例：

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

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

// 想法：先求出链表长度，然后用倒数算出正数(length - n + 1)
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length = 0;
        ListNode temp = head;
        while(temp != null){
            length++;
            temp = temp.next;
        }
        
        int target = length - n + 1;
        if(target == 1){
            head = head.next;
            return head;
        }
        
        ListNode pre = head;
        temp = head.next;
        int cur = 2;
        
        
        while(target != cur){
            pre = temp;
            temp = temp.next;
            cur++;
        }
        
        pre.next = temp.next;
        
        return head;
    }

     第一趟先求出链表长度，第二趟找到要求位置元素并删除，但用了两趟循环，下面看一种更好的算法

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        
        for(int i=1;i<=n+1;i++)
        {
            first = first.next;
        }
        while(first!= null)
        {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

    用了两个指针，第一个指针先走到第n个元素后，然后两个指针再一起走，当第一个指针走完链表（走了链表长度）时，第二个指针走了链表长度减n+1个元素，走到了倒数第n个元素前，此时使second.next = second.next.next;即可，循环了两次，但两次循环的总长度是链表的长度

    小结 - 链表中的双指针

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

// Initialize slow & fast pointers
ListNode slow = head;
ListNode fast = head;
/**
 * Change this condition to fit specific problem.
 * Attention: remember to avoid null-pointer error
 **/
while (slow != null && fast != null && fast.next != null) {
    slow = slow.next;           // move slow pointer one step each time
    fast = fast.next.next;      // move fast pointer two steps each time
    if (slow == fast) {         // change this condition to fit specific problem
        return true;
    }
}
return false;   // change return value to fit specific problem

    提示

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

    1. 在调用 next 字段之前，始终检查节点是否为空。

    获取空节点的下一个节点将导致空指针错误。例如，在我们运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。

    2. 仔细定义循环的结束条件。

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

    复杂度分析

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

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

1. 如果没有循环，快指针需要 N/2 次才能到达链表的末尾，其中 N 是链表的长度。
2. 如果存在循环，则快指针需要 M 次才能赶上慢指针，其中 M 是列表中循环的长度。

    显然，M <= N 。所以我们将循环运行 N 次。对于每次循环，我们只需要常量级的时间。因此，该算法的时间复杂度总共为 O(N)。

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

亲爱的读者：有时间可以点赞评论一下