鏈表中環的入口節點

02-12

鏈表中環的入口節點

如果鏈表中包含環，如何找到入口節點？

思路：定義2個指針pfast和pslow，pfast指針每次走2步，pslow指針每次走1步，

如果走的快的指針最後追上走的慢的指針，則鏈表成環。

設:

慢指針走過的路程為s

出發點距離環入口點為a

環中相遇點距離入口點為b(走過的)

2個等式判斷環的入口點：

1.快指針走的路程是慢指針的2倍。

2s = s + nr==>s = nr

2.慢指針走過的路程

a + b = s

聯合1,2：

a = nr - b

因此，指針1從環內相遇點開始走，指針2從起點開始走，它們相遇點就是環的入口點。

參考代碼：

root@gt:/home/git/Code# ./a.out 0 1 2 3 4 5 6 7 8 9 10 11 12 pfast:2 pslow:1pfast:4 pslow:2pfast:6 pslow:3pfast:8 pslow:4pfast:10 pslow:5pfast:12 pslow:6pfast:11 pslow:7pfast:10 pslow:8pfast:12 pslow:9pfast:11 pslow:10pfast:10 pslow:11pfast:12 pslow:12has:1 meeting node:12enrty node:10root@gt:/home/git/Code# cat ring.c #include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct listNode{ int value; struct listNode* pnext;}ListNode;ListNode* entryNode(ListNode* phead,ListNode* pnode){ if(phead == NULL || pnode == NULL) return NULL; while(phead != pnode) { phead = phead->pnext; pnode = pnode->pnext; } return phead;}int hasRing(ListNode* phead,ListNode** ppnode){ if(phead == NULL) return 0; int ring = 0; ListNode* pslow = phead->pnext; ListNode* pfast = pslow->pnext; while(pfast != NULL && pslow != NULL) { printf("pfast:%d pslow:%d ",pfast->value,pslow->value); if(pslow == pfast) { ring = 1; *ppnode = pslow; break; } pslow = pslow->pnext; pfast = pfast->pnext->pnext; } if(pfast == NULL) ring = 0; return ring;}int main(){ ListNode* phead = (ListNode*)malloc(sizeof(ListNode)); phead->value = 0; phead->pnext = NULL; ListNode* plast = phead; for(unsigned int i = 1;i < 11 ;i++) { ListNode* pnew = (ListNode*)malloc(sizeof(ListNode)); pnew->value = i; pnew->pnext = NULL; plast->pnext = pnew; plast = pnew; } ListNode* pringNode2 = (ListNode*)malloc(sizeof(ListNode)); pringNode2->value = 12; pringNode2->pnext = plast; ListNode* pringNode1 = (ListNode*)malloc(sizeof(ListNode)); pringNode1->value = 11; pringNode1->pnext = pringNode2; plast->pnext = pringNode1; ListNode* ptmp = phead; for(int i = 0;i < 13;i++) { printf("%d ",ptmp->value); ptmp = ptmp->pnext; } printf(" "); ListNode* pnode = NULL; int has = 0; has = hasRing(phead,&pnode); printf("has:%d meeting node:%d ",has,pnode->value); ListNode* pentry = entryNode(phead,pnode); printf("enrty node:%d ",pentry->value); return 0;}root@gt:/home/git/Code#