Leetcode 142. Linked List Cycle II(python+cpp)

题目

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.Note: Do not modify the linked list.

Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

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

解析

这题与141本质上是一样的，只是141只需要判断是否成环，而这边需要返回成环的节点位置。这两题的标准解法是Floyd’s Tortoise and Hare，这个算法分为两阶段，第一阶段就是141的题目，第二阶段则是142的题目

解法1：利用set

利用set, Treenode可以作为集合的元素，但是并不符合follow up

class Solution(object):def detectCycle(self, head):""":type head: ListNode:rtype: ListNode"""seen = []while head:if head in seen:return headseen.append(head)head = head.nextreturn None

时间复杂度：O(N)
空间复杂度：O(N)

解法2：Floyd’s Tortoise and Hare

Floyd算法分为两个阶段，阶段1判断是否成环，阶段2寻找成环的节点
阶段1：
设置快慢两个指针，慢指针每次向前移动一步，快指针每次移动两步，如果链表中有环的话，那么最后快慢指针一定会走到同一个节点，而这个节点就是intersection
阶段2：
再次设置两个指针，一个指针从头列表开始，另一个指针从阶段1找到的intersection开始，两个指针都一次向前移动一步，知道两个指针指向同一个节点，此时的节点便是成环的入口
具体的算法证明参考leetcode的官方solution

class Solution(object):def detectCycle(self, head):""":type head: ListNode:rtype: ListNode"""def getIntersection(head):tortoise = headhare = headwhile hare and hare.next:tortoise = tortoise.nexthare = hare.next.nextif tortoise == hare:return tortoisereturn Noneif not head:return None#phase 1intersect = getIntersection(head)if not intersect:return None#phase 2ptr1 = headptr2 = intersectwhile ptr1 != ptr2:ptr1 = ptr1.nextptr2 = ptr2.nextreturn ptr1

时间复杂度：O(N)
空间复杂度：O(1)

C++版本

注意do while的用法和返回空指针的表示方法

class Solution {
    
public:ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head,*fast=head;do{
    if (!fast || !fast->next) return nullptr;fast = fast->next->next;slow = slow->next;} while(fast!=slow);fast = head;while (fast!=slow){
    slow = slow->next;fast = fast->next;}return slow;}
};