剑指offer（专项突破版）4.3 双指针
分析
使用双指针，首先第一个指针指向头结点，然后走n步，第二个指针不动；第二个指针初始为哨兵结点，随后两个指针同时向后移动，由于两个指针之间相隔n个结点，即当第一个指针指向最后时，第二个指针为倒数第n+1个结点，删除倒数第n个结点，只需将第二个指针的next指向它的next的next。
代码
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
32
33
|
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* front = head;
ListNode* back = dummy;
for(int i = 0; i < n; i++){
front = front->next;
}
while(front != NULL){
front = front->next;
back = back->next;
}
back->next = back->next->next;
return dummy->next;
}
};
|
复杂度分析
时间复杂度：O(L)，其中L是链表的长度。
空间复杂度：O(1)。
需要知道环中节点数目的解法
定义两个指针并同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果链表中不包含环，走得快的指针直到抵达链表的尾节点都不会和走得慢的指针相遇。如果链表中包含环，走得快的指针在环里绕了一圈之后将会追上走得慢的指针。
如何找到环的入口节点，可以用两个指针来解决。先定义两个指针P1和P2，指向链表的头节点。如果链表中的环有n个节点，第1个指针P1先在链表中向前移动n步，然后两个指针以相同的速度向前移动。当第2个指针P2指向环的入口节点时，指针P1已经围绕环走了一圈又回到了入口节点。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
class Solution {
public:
ListNode *getInLoop(ListNode *head){
if(head == NULL || head->next == NULL){
return NULL;
}
ListNode *slow = head->next;
ListNode *fast = slow->next;
while(slow != NULL && fast != NULL){
if(slow == fast){
return slow;
}
slow = slow->next;
fast = fast->next;
if(fast){
fast = fast->next;
}
}
return NULL;
}
ListNode *detectCycle(ListNode *head) {
ListNode *inLoop = getInLoop(head);
if(inLoop == NULL){
return NULL;
}
int len = 1;
for(ListNode *temp = inLoop->next;temp != inLoop;temp=temp->next){
len++;
}
ListNode *fast = head;
for(int i = 0; i < len; i++){
fast = fast->next;
}
ListNode *slow = head;
while(slow != fast){
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
|
不需要知道环中节点数目的解法
如果链表中有环，快慢两个指针一定会在环中的某个节点相遇。慢的指针一次走一步，假设在相遇时慢的指针一共走了k步。由于快的指针一次走两步，因此在相遇时快的指针一共走了2k步。因此，到相遇时快的指针比慢的指针多走了k步。另外，两个指针相遇时快的指针比慢的指针在环中多转了若干圈。也就是说，两个指针相遇时快的指针多走的步数k一定是环中节点的数目的整数倍，此时慢的指针走过的步数k也是环中节点数的整数倍。
此时可以让一个指针指向相遇的节点，该指针的位置是之前慢的指针走了k步到达的位置。接着让另一个指针指向链表的头节点，然后两个指针以相同的速度一起朝着指向下一个节点的指针移动，当后面的指针到达环的入口节点时，前面的指针比它多走了k步，而k是环中节点的数目的整数倍，相当于前面的指针在环中转了k圈后也到达环的入口节点，两个指针正好相遇。也就是说，两个指针相遇的节点正好是环的入口节点。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
class Solution {
public:
ListNode *getInLoop(ListNode *head){
if(head == NULL || head->next == NULL){
return NULL;
}
ListNode *slow = head->next;
ListNode *fast = slow->next;
while(slow != NULL && fast != NULL){
if(slow == fast){
return slow;
}
slow = slow->next;
fast = fast->next;
if(fast){
fast = fast->next;
}
}
return NULL;
}
ListNode *detectCycle(ListNode *head) {
ListNode *inLoop = getInLoop(head);
if(inLoop == NULL){
return NULL;
}
ListNode *fast = inLoop;
ListNode *slow = head;
while(fast != slow){
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
|
时间复杂度分析：
getInLoop() 函数的时间复杂度与之前相同，为 O(n)，其中 n 是链表的长度，因为在最坏情况下，慢指针需要遍历整个链表一次才能确定是否有环。
detectCycle() 函数中，先调用 getInLoop() 函数，然后直接使用两个指针在链表中移动直到相遇。由于在 getInLoop() 中已经找到了环中的结点，所以这里不再需要计算环的长度，直接从相遇点开始移动一个指针，一个指针从头开始，它们相遇的点就是环的起始节点。
因为在最坏情况下，两个指针都需要遍历环一次才能相遇，所以时间复杂度为 O(n)。
因此，总的时间复杂度为 O(n)。
空间复杂度分析：
- 与之前相同，算法中使用了常数个额外指针变量和常数个额外整型变量，所以空间复杂度为 O(1)。
构造带环链表解法
借鉴上一题的思路，把第二条链表的末尾连到头上，就形成了上一题中的情况。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
class Solution {
public:
ListNode *getInLoopNode(ListNode *head){
if(!head || !head->next){
return NULL;
}
ListNode *slow = head->next;
ListNode *fast = slow->next;
while(slow && fast){
if(slow == fast){
return slow;
}
slow = slow->next;
fast = fast->next;
if(fast){
fast = fast->next;
}
}
return NULL;
}
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(!headA || !headB){
return NULL;
}
ListNode *node = headA;
while(node->next){
node = node->next;
}
node->next = headB;
ListNode *inLoop = getInLoopNode(headA);
if(!inLoop){
return NULL;
}
ListNode *fast = inLoop;
ListNode *slow = headA;
while(fast != slow){
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
|
但是这种方法无法通过测试，原因是改变了链表的结构。
双指针方法
首先遍历两个链表得到它们的长度，这样就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第2次遍历时，第1个指针P1在较长的链表中先移动若干步，再把第2个指针P2初始化到较短的链表的头节点，然后这两个指针按照相同的速度在链表中移动，直到它们相遇。两个指针相遇的节点就是两个链表的第1个公共节点。
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
32
33
34
35
36
37
38
39
40
|
class Solution {
public:
int getListLen(ListNode *head){
int len = 0;
while(head){
head = head->next;
len++;
}
return len;
}
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int m = getListLen(headA);
int n = getListLen(headB);
int delta = abs(m-n);
ListNode *longer = m > n ? headA : headB;
ListNode *shorter = m > n ? headB : headA;
ListNode *p1 = longer;
for(int i = 0; i < delta; i++){
p1 = p1->next;
}
ListNode *p2 = shorter;
while(p1 != p2){
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
};
|
- 时间复杂度：上述代码将两个链表分别遍历两次，第1次得到两个链表的节点数，第2次找到两个链表的第1个公共节点，这种方法的时间复杂度是O（m+n）
- 空间复杂度：由于不需要保存链表的节点，因此这种方法的空间复杂度是O（1）。
总结
双指针思路又可以根据两个指针不同的移动方式细分成两种不同的方法。第1种方法是前后双指针，即一个指针在链表中提前朝着指向下一个节点的指针移动若干步，然后移动第2个指针。前后双指针的经典应用是查找链表的倒数第k个节点。先让第1个指针从链表的头节点开始朝着指向下一个节点的指针先移动k-1步，然后让第2个指针指向链表的头节点，再让两个指针以相同的速度一起移动，当第1个指针到达链表的尾节点时第2个指针正好指向倒数第k个节点。
第2种方法是快慢双指针，即两个指针在链表中移动的速度不一样，通常是快的指针朝着指向下一个节点的指针一次移动两步，慢的指针一次只移动一步。采用这种方法，在一个没有环的链表中，当快的指针到达链表尾节点的时候慢的指针正好指向链表的中间节点。