首页 > 代码库 > leetcode - Linked List Cycle II

leetcode - Linked List Cycle II

2024-07-10 03:51:20   220人阅读

题目：Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

 

这道题是找链表环的后续，说实话这题真没想到什么比较好的方法，可以有空间复杂度为O(n)的算法，但是实在太low，就不讲了

网上查找到了符合题意的算法，链接：http://blog.csdn.net/sysucph/article/details/15378043，具体的证明可以看看链接里的内容，我这里就讲下具体做法

思路：

1、快慢指针，第一次在环里相遇时，将快指针重新放回到链表开头，并且以每次一步的速度走，当这两个指针再次相遇时，就会停在环的起始节点

代码：

 1 #include <stddef.h> 2  3 struct ListNode 4 { 5     int val; 6     ListNode *next; 7     ListNode(int x) : val(x), next(NULL) {}; 8 }; 9 10 class Solution11 {12 public:13     ListNode* detectCycle(ListNode *head)14     {15         if (!head)16         {17             return NULL;18         }19 20         ListNode *one = head;21         ListNode *two = head;22 23         while (true)24         {25             one = one->next;26             two = two->next;27             if (!two)28             {29                 return NULL;30             }31             two = two->next;32             if (!two)33             {34                 return NULL;35             }36             //快慢指针相遇，证明有环37             if (two == one)38             {39                 two = head;40                 while (two != one)41                 {42                     two = two->next;43                     one = one->next;44                 }45 46                 return one;47             }48         }49     }50 };51 52 int main()53 {54     return 0;55 }
View Code

 


联系
我们