单链表含环问题总结:
给定一个单链表,只给出头指针h:
1、如何判断是否存在环?2、如何知道环的长度?3、如何找出环的连接点在哪里?4、带环链表的长度是多少?解法:1、对于问题1,使用追赶的方法,设定两个指针slow、fast,从头指针开始,每次分别前进1步、2步。如存在环,则两者相遇;如不存在环,fast遇到NULL退出。2、对于问题2,记录下问题1的碰撞点p,slow、fast从该点开始,再次碰撞所走过的操作数就是环的长度s。3、问题3:有定理:碰撞点p到连接点的距离=头指针到连接点的距离,因此,分别从碰撞点、头指针开始走,相遇的那个点就是连接点。4、问题3中已经求出连接点距离头指针的长度,加上问题2中求出的环的长度,二者之和就是带环单链表的长度有了上面的指导思想,这道题很好解,要是不知道就麻烦了。
1 #include2 using namespace std; 3 struct ListNode { 4 int val; 5 ListNode *next; 6 ListNode(int x) : val(x), next(NULL) {} 7 }; 8 class Solution { 9 public:10 bool hasCycle(ListNode *head) {11 ListNode *slow,*fast;12 if(head == NULL || head->next == NULL || head->next->next == NULL) return false;13 slow = head->next;14 fast = head->next->next;15 while(fast != NULL && fast->next != NULL && slow != fast){16 slow = slow->next;17 fast = fast->next->next;18 }19 if(fast == NULL || fast->next == NULL) return false;20 if(slow == fast) return true;21 }22 23 ListNode *detectCycle(ListNode *head) {24 ListNode *slow,*fast;25 if(head == NULL || head->next == NULL || head->next->next == NULL) return NULL;26 slow = head->next;27 fast = head->next->next;28 while(fast != NULL && fast->next != NULL && slow != fast){29 slow = slow->next;30 fast = fast->next->next;31 }32 if(fast == NULL || fast->next == NULL) return NULL;33 if(slow == fast){34 ListNode *cur = head;35 while(cur != slow){36 cur = cur->next;37 slow = slow->next;38 }39 return cur;40 }41 }42 };