链表中环的入口结点

1. 题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

2. 思路

• 用set记录走过的节点
• 快慢指针：一个走两步，一个走一步，如果没有cycle那么不会相遇，有cycle就会相遇

3. 实现

3.1. set法

• java

public class 链表中环的入口结点
{
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        //检查参数
        if (pHead == null)
        {
            return null;
        }
        //把Node放入Set中
        Set<ListNode> set = new HashSet<>();
        //遍历的时候看Set中是否有，有的话肯定是环的入口节点
        ListNode current = pHead;
        while (current != null)
        {
            if (set.contains(current))
            {
                return current;
            }
            set.add(current);
            current = current.next;
        }

        return null;
    }
}

• go

//时间复杂度：O(n)
//空间复杂度：O(n)，最坏情况下，单链表的所有结点都在存入set
func EntryNodeOfLoop(pHead *ListNode) *ListNode {
	if pHead == nil {
		return nil
	}

	m := make(map[*ListNode]interface{})
	n := pHead
	for n != nil {
		_, ok := m[n]
		if ok {
			return n
		}
		m[n] = nil
		n = n.Next
	}

	return nil
}

3.2. 快慢指针

//时间：O(N)
//空间：O(1)
func EntryNodeOfLoop2(pHead *ListNode) *ListNode {
	if pHead == nil {
		return nil
	}

	fast := pHead
	slow := pHead

	for slow != nil && fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			current := pHead
			for current != slow {
				current = current.Next
				slow = slow.Next
			}
			return current
		}
	}

	return nil
}

4. 参考

• 链表中环的入口结点_牛客网
• LCR 022. 环形链表 II - 力扣（LeetCode）