双指针技巧

双指针有两类:

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

快慢指针


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

判断链表中是否存在环

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

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

  • 如果链表不存在环,那么快指针最终会运行到链表的终端节点
  • 如果链表存在环,那么快指针会多跑一会然后追上慢指针,此时说明链表存在环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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的距离是相等的。因此我们的算法代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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个指针都指向链表头部,然后慢指针每次走一步,快指针每次走两步,当快指针到达链表结尾时,慢指针的位置就是链表的中间节点。

1
2
3
4
5
6
7
8
9
10

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步而已。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×