双指针法的应用

LC142.环形链表Ⅱ

分析： 为什么slow\fast指针一定会相遇？ 为什么之后从Head开始的指针一定会和slow在环的入口出相遇？

1. 如下代码所示，首先排除无环的情况，那么有环的情况下，fast每一步都比slow多走一步，类比操场跑步的情景可感性的推断出，fast一定会在环内的某一点与slow相遇（套圈）。
2. 当fast与slow相遇的时候，设slow走了n步，则fast走了2n步，fast比slow多走的n步，而且fast比slow多走的这n步一定是环长的整数倍，可以画图帮助理解。
3. 引用力扣评论，解答了为什么一定会在慢指针走环的第一圈时候相遇，非常直观。

之所以慢指针跑一圈的过程中，快指针一定能追上是因为：（极限思想） 假设他们都是从入环点开始跑的，那么当慢指针刚好跑完一圈时，快指针刚好跑完两圈，也是在一圈的末尾追上慢指针。而现实情况往往是在慢指针到入环处时快指针已经入环并走了了，所以实际情况一定会在第一圈之内相遇。

• 基于上述3点分析，各长度如下图所示，则 S_fast = a + b + c + b, S_slow = a + b;又S_fast = 2 * S_slow,所以可以得到 a = c ; 所以才有了之后将fast置于head处，之后再与slow同时一步一进开始走，必会在入环节点出相遇。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        if (head == null || head.next == null) {
            return null;
        }
        do {
            if (fast == null || fast.next == null) {
                //走到头了，说明没有环路
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

剑指offer21.删除链表的倒数第n个结点

剑指offer21

• Tips：链表的题目常常使用dummy虚拟节点来操作，便于删除首节点等操作。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head), second = dummy, first = head; 
        for (int i = 0; i < n; i++) {
            //first & second 之间有n个节点，不算两边
            first = first.next;
        }
        //second会停留在倒数第n+1个节点的位置
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}