题解 | #链表中环的入口结点#

链表中环的入口结点

http://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4

算法思想一：双指针

解题思路：

我们使用两个指针，fast 与 slow。

1、它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。

2、当发现 slow 与 fast 相遇时，我们再额外使用一个指针 cur。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇

图解：

代码展示：

Python版本

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if not pHead:
            return None
        if pHead.next:
            slow = pHead.next
            fast = pHead.next.next
        else:
            return None
        
        while fast:
            if fast != slow:
                # 快指针走两步
                if fast.next:
                    fast = fast.next.next
                else:
                    return None
                # 慢指针走一步
                slow = slow.next
            else:
                # 当两指针相同时，则从头节点同时出发，当相遇即为入环口
                cur = pHead
                while cur != slow:
                    slow = slow.next
                    cur = cur.next
                return cur
        return None

复杂度分析：

时间复杂度O(N)：其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度

空间复杂度O(1)：额外使用的指针占用常数空间

算法思想二：哈希表

解题思路：

我们遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现

1、遍历链表，并将访问过的结点存储到哈希表中

2、判断结点是否在哈希表中，若存在则返回当前结点

3、遍历结束，则返回 null

代码展示：

JAVA版本

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode pos = pHead;
        // 哈希表记录访问过的结点
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            // 判断结点是否被访问
            if (visited.contains(pos)) {
                return pos;
            } else {
                // 结点记录添加到哈希表中
                visited.add(pos);
            }
            // 遍历
            pos = pos.next;
        }
        return null;
    }