双指针技巧

双指针有两类:

  • 快慢指针
    • 一般用于解决链表相关的问题,如判断链表是否存在环
  • 左右指针
    • 一般用于解决数组相关的问题,如二分查找

快慢指针


快慢指针一般都初始化指向链表的头结点 head,前进时快指针 fast 在前,慢指针 slow 在后,巧妙解决一些链表中的问题。

判断链表中是否存在环

因为单链表的特点是每个节点只知道下一个节点,所以一个指针的话无法判断链表中是否含有环的。

使用快慢指针的思想解决链表中是否存在环的问题,其实是非常简单的,快慢指针初始时都指向链表头结点,慢指针每次前进一步,快指针每次前进两步。

  • 如果链表不存在环,那么快指针最终会运行到链表的终端节点
  • 如果链表存在环,那么快指针会多跑一会然后追上慢指针,此时说明链表存在环。
boolean hasCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;

    while(fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        if (fast == slow) {
            return true;
        }
    }
    return false;
} 

已知链表中存在环,返回环的的起始位置

< br />
关于计算环的起点这个,需要用到一点的数学知识,我们假定快慢指针在4这个位置相遇了。同时我们做如下约定:

  • 表头1到环起点3之间的距离我们记录为m
  • 节点3和节点4之间的距离我们记录为n
  • 环的长度我们记录为r
  • slow指针从表头1到当前位置4一共经过的距离我们记录为k

因此我们会有如下结论:

  • slow指针走的距离为k, 我们很容易得出k=m+n,那么fast指针走的距离就会是2k, 假定相遇时fast走了p圈,所以fast指针走的距离为:m + pr + n
  • 根据上一步的推理,我们会有如下的等式:pr + n + m = 2k = 2m + 2n
  • 所以pr = m + n. 所以我们可以得出,节点4顺时针到节点3的距离为 pr - n = m。其实可以推断出p = 1的。所以节点4顺时针到节点3的距离和节点1到节点3的距离是相等的。因此我们的算法代码如下:
boolean getCycleStartPosition(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        //第一次相遇推出循环
        if (fast == slow) {
            break;
        }
    }

    //将慢指针设置为起点,然后快慢指针都每次走一步
    slow = head;
    while(slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

寻找链表中间节点


这个问题的解法思路也是用快慢指针,期初2个指针都指向链表头部,然后慢指针每次走一步,快指针每次走两步,当快指针到达链表结尾时,慢指针的位置就是链表的中间节点。


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

当链表的长度是奇数时,slow 恰巧停在中点位置;如果长度是偶数,slow 最终的位置是中间偏右

寻找链表的倒数第 k 个元素

这个问题换是快慢指针的事情,这次快慢指针都是每次走一步,但是得先让快指针提前走k步而已。

ListNode getLastKNode(ListNode head, int k) {
    if (head == null || k < 0) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;

    for(int i = 0; i < k; i++) {
        fast = fast.next;
        if (fast == null) {
            return null;
        }
    }

    while(fast != null && fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}
comments powered by Disqus