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

/*双指针法*/
/*
* 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;
}

最后

以上就是舒适小懒虫为你收集整理的链表必学算法（四）：双指针法的全部内容，希望文章能够帮你解决链表必学算法（四）：双指针法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。