首页 > 代码库 > Linked List Cycle

Linked List Cycle

141. Linked List Cycle

题目链接:https://leetcode.com/problems/linked-list-cycle/#/description

题目大意:给定一个链表,判断是否有环,要求不能申请额外的空间

 

思路:使用快慢指针。fast指针一次移动两步,slow指针一次移动一步。如果有环,则fast一定会和slow相遇。可以假设fast越过了slow而没有相遇,且slow出于位置i,fast处于位置i+1,那么,在前一步,slow就处于位置i-1,fast处于位置((i+1)-2)或i-1。也就是说,两者相遇了。假定这个链表有一部分不存在环路,长度为k。slow没走p步,fast就会走2p步。因此slow走了k步进入环路部分时,fast已经总共走了2k步,进入环路部分已有k步。由于k可能比环路长度大得多,实际上应该为mod(k, loop_len),并用k表示。即slow处于环中的0步位置,fast处于环中的k步位置,slow落后于fast,相距k步,或者说fast落后于slow,相距loop_len-k步。从fast落后于slow来看,fast现在落后slow loop_len-k步,并且每经过一个移动,fast就走近slow一步,那么两者将在loop_len-k次移动之后相遇。

算法复杂度:时间复杂度O(n),空间复杂度O(1)

代码:

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     bool hasCycle(ListNode *head) {
12         ListNode *slow = head, *fast = head;
13         while (fast && fast->next) {
14             slow = slow->next;
15             fast = fast->next->next;
16             if (slow == fast)
17                 return true;
18         }
19         return false;
20     }
21 };

评测系统上运行结果:

技术分享

 

142. Linked List Cycle II

题目链接:https://leetcode.com/problems/linked-list-cycle-ii/#/description

题目大意:给定一个链表,如果有环,返回环的起点,如果没环,返回nullptr。要求不能修改链表。

 

思路:使用快慢指针。fast指针一次移动两步,slow指针一次移动一步。如果有环,则fast一定会和slow相遇。可以假设fast越过了slow而没有相遇,且slow出于位置i,fast处于位置i+1,那么,在前一步,slow就处于位置i-1,fast处于位置((i+1)-2)或i-1。也就是说,两者相遇了。假定这个链表有一部分不存在环路,长度为k。slow没走p步,fast就会走2p步。因此slow走了k步进入环路部分时,fast已经总共走了2k步,进入环路部分已有k步。由于k可能比环路长度大得多,实际上应该为mod(k, loop_len),并用k表示。即slow处于环中的0步位置,fast处于环中的k步位置,slow落后于fast,相距k步,或者说fast落后于slow,相距loop_len-k步。从fast落后于slow来看,fast现在落后slow loop_len-k步,并且每经过一个移动,fast就走近slow一步,那么两者将在loop_len-k次移动之后相遇。假设这个位置为meetspot,meetspot与环路起始处相距k个结点,同时知道链表的头部距离环路起始处也是k个结点。若用一个指针指向meetspot,另一个指针指向链表的头部,两者与环路起始处均相距k个结点,以同样的速度移动,这两个指针就会在k步之后相遇在环路的起始处。

算法复杂度:时间复杂度O(n),空间复杂度O(1)

代码:

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *detectCycle(ListNode *head) {
12         ListNode *slow = head, *fast = head;
13         while (fast && fast->next) {
14             slow = slow->next;
15             fast = fast->next->next;
16             if (slow == fast) {
17                 fast = head;
18                 while (slow != fast) {
19                     slow = slow->next;
20                     fast = fast->next;
21                 }
22                 return fast;
23             }
24         }
25         return nullptr;
26     }
27 };

评测系统上运行结果:

技术分享

 

Linked List Cycle