|
有环链表问题及其证明 (2011-06-16 10:50:27)转载▼ 标签： 杂谈 分类： 算法学习 三种解决方法： 第一种方法，将所有的遍历过的节点用某个结构存储起来，然后每遍历一个节点，都在这个结构中查找是否遍历过，如果找到有重复，则说明该链表存在循环；如果直到遍历结束，则说明链表不存在循环。 这个结构我们可以使用hash来做，hash中存储的值为节点的内存地址，这样查找的操作所需时间为O(1)，遍历操作需要O(n)，hash表的存储空间需要额外的O(n)。所以整个算法的时间复杂度为O(n)，空间复杂度为O(n)。 第二种方法，比较的特别，是使用反转指针的方法，每过一个节点就把该节点的指针反向。 当有环的时候，最后指针会定位到链表的头部，如果到最后，都没有再到头部，那说明链表不存在循环。 这个方法会破坏掉链表，所以如果要求是不能破坏链表的话，我们最后就还需要反转一下，再将链表恢复。 这个方法使用的空间复杂度为O(1)，其实是使用了3个指针，用于进行反转。同时，时间复杂度为O(n)。 第三种方法，可能大家已经知道了，同时也是面试官大多想要得到的答案，就是快慢指针。 快指针pf(f就是fast的缩写)每次移动2个节点，慢指针ps(s为slow的缩写)每次移动1个节点，如果快指针能够追上慢指针，那就说明其中有一个环，否则不存在环。 这个方法的时间复杂度为O(n)，空间复杂度为O(1)，实际使用两个指针。 快慢指针判别是否有环(分别为指针low和fast）证明过程： 假设该链表在环出现之前有L个结点，环中有C个结点。 再假设慢指针初始化时指向的位置为a、快指针初始化时指向的位置为b， 如果二者在t 次移动后相遇，也就是说：(a+t-L)
mod C == (b+2*t-L) mod C, 所以无论a、b的起始位置如何，二者总是会相遇的。 推导：(a+t-L) mod C == (b+2*t-L) mod C a+t-L-m*C == b+2*t-L -n*C t == (a-b) - (m-n)*C a==b ==> t ==
(n-m)*C；在保证m和n为正整数的情况下上式t有正整数解。 若两个指针的步长分别为：x和y（即每走一步步长分别为：x*t和y*t） (x-y)*t == (a-b)
- （m-n)*C 要是程序不陷入死循环必须满足上面这个等式有正整数解。 比方说：假设链表是由4个结点首尾相接构成的一个圆圈（编号为0~3） 慢指针初始位置在0，每次前进1步； 快指针初始位置在3，每次前进3步； 有：（3-1）*t ==
(3-0) - （m-n）*4 此等式没有正整数解，所以虽然这两个指针也是一快一慢一前一后，但它们永远也不会相遇！ 寻找环的入口。 在x=1，y=2，a=b=0的情况下，让fast回到链表的头部，重新走，每次步长走1， 那么当low和fast再次相遇的时候，就是环路的入口了。 t = (n-m)*C 假设再走t1步：(t+t1-L)
mod C == 0 ==> t1 == L 测试代码： #include <iostream> using namespace std; typedef struct Node { int num; Node* next; }SNode; //带头节点 void creatList(SNode** s, int len, int c) { int pos = 0; int l = len; SNode *p, *q; *s = new SNode; (*s)->num = -1; (*s)->next = NULL; q = *s; while(l--) { p = new SNode; p->num = pos++; p->next = NULL; q->next = p; q = q->next; } if( c >= 0
&& c < len ) { q = *s; while( c >= 0 ) { --c; q = q->next; } p->next = q; } } //不带头节点 void creatList1(SNode** s, int len, int c) { int pos = 0; int l = len; SNode *p, *q; *s = new SNode; (*s)->num = pos++; (*s)->next = NULL; --l; q = *s; while(l--) { p = new SNode; p->num = pos++; p->next = NULL; q->next = p; q = q->next; } if( c >= 0
|| c < len ) { q = *s; while( c-- ) { q = q->next; } p->next = q; } } void printList(SNode *s, int len) { SNode *p = s; while(p
&& len--) { cout << p->num << "
"; p = p->next; } cout << endl; } SNode* checkList(SNode *s) { bool flag = false; SNode *low, *fast; low = s; fast = s; while( low != NULL
&& fast != NULL ) { low = low->next; fast = fast->next->next; if( low == fast ) { flag = true; break; } } if( flag ) { fast = s; while( low != fast ) { low = low->next; fast = fast->next; } return low; } return NULL; } int main() { SNode *s; SNode *p;
creatList1(&s, 20, 13); printList(s, 25); p =
checkList(s); cout << p->num << endl; return 0; } |
|
|
