链表必学算法（四）：双指针法

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/*双指针法*/
/*
* SCs in different cases
* author: Whywait
*/
typedef struct node {
Elemtype data;
struct node* next;
} Lnode;
/*case ONE*/
bool count_Kth_backwards(Linklist& L, int k) {
// if the node counted Kth backwards exit,
//
print it and return true
// else return false
Lnode* quick = L, * slow = L;
while (k && quick) {
quick = quick->next;
k--;
}
if (k) return false;
while (quick) {
quick = quick->next;
slow = slow->next;
}
print(slow->data);
return true;
}
/*case TWO*/
Lnode* node_into_circle(Linklist& L) {
// whether the slists have a circle
// if true, return the pointer to the node first node passed in the circle
// if not, return NULL
Lnode* slow = L, * quick = L;
while (true) {
if (!quick->next || !quick->next->next) return false;
quick = quick->next->next;
slow = slow->next;
if (quick == slow) break;
}
quick = L;
while (quick != slow) {
quick = quick->next;
slow = slow->next;
}
return quick;
}
/*case THREE*/
Lnode* find_first_public_node(Linklist& LA, Linklist& LB) {
// LA and LB have a public part
// we need to find the first node in public part and return it
// if don't have a public part, return NULL
Lnode* pa = LA, * pb = LB;
int lengthA = 0, lengthB = 0, count = 0;
while (pa) {
pa = pa->next;
lengthA++;
count++;
}
while (pb) {
pb = pb->next;
lengthB++;
}
pa = PB; pb = PA;
while (pa != pb && count < lengthA + lengthB) {
pa = pa->next;
pb = pb->next;
count++;
}
if (pa == pb) pa;
else return NULL;
}