带环链表
版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~
Linked List Cycle I
Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?
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?
-
题目大意：（I）给定一个链表，判断这个单链表中是否有环。（II）给定一个单链表，返回单链表的环的起点。如果单链表中没有环，返回
null。进一步考虑：你能解决这两个问题但是不用额外的空间吗？ps：意思就是让你不要用额外的空间。 -
（I）思路：对于第一个问题，我一开始觉得，设置两个指针，一个指向头结点，一个向后查找，如果重新查找到了头结点，就说明有环，但是，情况并非都是这么理想的，比如：
看到这种情况，就想自己果然还是太年轻了，于是就想到用HashSet，每访问一个节点，就将其记录下来，第一次重复访问了某一个节点时，就说明链表有环，而且该点就是环的起点。
public boolean hasCycle2(ListNode head) {
if (head == null) {
return false;
}
HashSet<ListNode> set = new HashSet<ListNode>();
while (head != null) {
if (set.contains(head)) {
return true;
}
set.add(head);
head = head.next;
}
return false;
}
-
然而建立哈希表需要额外
O(n)的空间开销，于是开始搜集资料，找到了快慢指针这一概念，就是定义两个指针fast和slow从起点开始，fast每次走两步，slow每次走一步，相遇则说明有环。 -
meng：而它们相遇的这个点，一定处于环的内部，并且与头节点的距离是环长度的整数倍记快慢指针相遇的这个点是Xv，一定有v≥μ且v=kλ。于是，寻找环的起点就不难了，因为起点μ一定满足xμ=xμ+v。我们只要从头节点开始遍历链表，第一个满足这个等式的节点就是环的起点。
-
上面的方法就是所谓的Floyd’s cycle-finding algorithm。算法的时间复杂度是O(μ+λ)O(μ+λ)，空间复杂度是O(1)。
- 代码
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool hasCycle(ListNode *head)
{
ListNode *fast, *slow;
fast = slow = head;
while(fast && fast->next)
{
fast = fast -> next -> next;
slow = slow -> next;
//快慢指针相遇说明有环
if(fast == slow)
return true;
}
return false;
}
};
-
（II）思路：如果有环（即
isCycle为true），则一个指针从头开始，另一个从xv开始，同时以相同的速度往前移动，每次都移动一步。当两个指针相遇时，位置就是环的起点。 -
代码：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool hasCycle(ListNode *head)
{
ListNode *fast, *slow;
fast = slow = head;
bool isCycle = false;
while(fast && fast->next)
{
fast = fast -> next -> next;
slow = slow -> next;
if(fast == slow)
{
isCycle = true;
break;
}
}
if(isCycle)
{
fast = head;
while(fast != slow)
{
fast = fast -> next;
slow = slow -> next;
}
return fast;
}
return NULL;
}
};
另外，如果还要求环的长度（最小正周期），由于已经知道了环的起点，只要从它开始遍历，找到第一个等于起点的位置即可，最多还需要O(λ)的时间。
版权声明：本文为博主原创文章，转载请注明出处。 个人博客地址：https://yangyuanlin.club 欢迎来踩~~~~
