单链表中圆环的开始节点

单链表中圆环的开始节点

问题

这个题目说的是，给你一个单链表，你要返回这个链表中，圆环的开始节点。如果单链表无环，就返回空指针。

比如说，给你的单链表是：

1 -> 2 -> 4 -> 8 -> 2
// 最后的 2 和前面的 2 是同一个节点

这个链表中存在环，并且环的开始节点是 2，于是你要返回节点 2。

代码

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public ListNode startNodeOfCycleHashSet(ListNode head) {
    Set<ListNode> set = new HashSet<>();
    for (ListNode p = head; p != null; p = p.next) {
      if (set.contains(p)) return p;
      set.add(p);
    }
    return null;
  }

  // Time: O(n), Space: O(1)
  public ListNode startNodeOfCycleTwoPointer(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
      fast = fast.next.next;
      slow = slow.next;
      if (fast == slow) {
        for (ListNode p = head; p != slow; p = p.next, slow = slow.next);
        return slow;
      }
    }
    return null;
  }

}