LeetCode -- 109 and 142

本文通过LeetCode 109 和 142来介绍快慢指针的技巧。

LeetCode 109

Description

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

1
2
3
4
5
6
7
8
9
Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

0
/ \
-3 9
/ /
-10 5

Solution

构建BST的关键在于定位到中点,这里有两种思路:

  1. 将链表转换成数组

    数组定位中点的效率是$O(1)$,所以算法复杂度是$O(N)$,但是需要$O(N)$的额外空间。

  2. 直接在链表上做

    链表定位中点的效率是$O(N)$,所以算法复杂度是$O(N\log N)$,只需要$O(1)$的辅助空间。

如何在链表上找到中点,直接的做法是先扫一边得到长度$N$,然后在扫到$\frac{N}{2}$即可。

有一种巧妙的技巧——快慢指针。同时维护两个指针fast,slow,两个指针的运动速度可以调整。在这个问题中,设置$v(fast) = 2, v(slow) = 1$即可。

Python Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
if head is None:
return None
p = q = head
last = None
while p and p.next:
p = p.next.next
last, q = q, q.next
lc = None
if last:
last.next = None
lc = self.sortedListToBST(head)
rc = self.sortedListToBST(q.next)
root = TreeNode(q.val)
root.left = lc
root.right = rc
return root

LeetCode 142

Description

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

img

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

img

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

img

Follow up:
Can you solve it without using extra space?

Solution

如果允许使用$O(N)$的额外空间,直接构建一个set即可。

不使用额外空间的前提下,只能使用几个指针呢,想要找到环,很自然的想到快慢指针。设置$v(fast)=2, v(slow)=1$,如果能相遇,说明存在环。

问题是,如果存在环,一定能相遇吗?什么时候能相遇?在什么地方相遇?

下面通过简单的分析来回答上述问题。

不妨设起点是$S$,环的起点是$O$,第一次相遇的地点是$T$,设$d(S,O) = A, d(O, T) = B, d(O, O) = C$。其中$C​$表示环的长度。

那么显然第一次相遇的条件是:

$$\frac{A + B + k_1 C}{2} = \frac{A + B + k_2 C}{1}$$

化简得

$$(k_1 - 2k_2)C = A + B$$

有一个隐含约束:$0 \leq B < C$

这里有两种情况

  1. 若$C > A$,那么显然解是$k_1 = 1, k_2 = 0, B = C - A$。
  2. 若$C \leq A$,那么显然解是$k_2 = 0, k_1 = \lfloor \frac{A}{C}\rfloor, B = A \mod C$。

可以发现,两种情况的解$k_2$都是$0$,说明第一次相遇时,慢指针没有走完一圈,时间复杂度一定是$O(N)$的。

接下来的问题是,相遇点是$T$,而不是$O$,怎么找到$O$。

答案很简单,相遇之后,将$fast$指针指向$S$,速度设为$1$,然后继续跑,再次相遇就是$O$。

原因很简单,因为

$$A = (C - B) + (k_1 - 2k_2 - 1)C$$

CPP Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == NULL) {
return NULL;
}
auto p = head, q = head;
do {
if (p->next == NULL || p->next->next == NULL) {
return NULL;
}
p = p->next->next;
q = q->next;
} while (p != q);
for (p = head; p != q; p = p->next, q = q->next);
return p;
}
};
------ 本文结束------
0%