基础算法之快慢指针

快慢指针即使用一快一慢两个指针，对链表进行遍历。利用两个指针的速度差，如2倍速-用于求中间指针或循环链表；恒定n个差值，用于寻找倒数第n个指针。

1. 环形链表

如果快指针到达NULL，说明链表以NULL结尾，不存在环。如果快指针追上慢指针，则表示有环。

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

2. 找中间值

我们把一个链表看成一个跑道，假设a的速度是b的两倍，那么当a跑完全程后，b刚好跑一半，以此来达到找到中间节点的目的。

publicListNode endOfFirstHalf(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

3. 删除倒数第N个节点

快指针先走n步，慢指针开始和快指针同步移动到next，当快指针到达链表尾部时，慢指针刚好移动到倒数第n-1个节点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode fast = head;
    ListNode slow = head;
    //慢指针比快指针慢N步,那么快指针指向末尾的null时,慢指针刚好指向要删除结点的前驱结点
    while (fast.next != null) {
        fast = fast.next;
        if (n == 0) {
            slow = slow.next;
        } else {
            n--;
        }
    }
    if (n != 0) { //没追上,说明删除的是头指针
        return head.next;
    } else {
        slow.next = slow.next.next;
    }
    return head;

}

总结

快慢指针在链表类的迭代中，时间复杂度是O(n)的量级，是一种能有效控制时间复杂的算法。