P94 单链表中圆环的开始节点

描述#

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

比如说，给你的单链表是：
1 -> 2 -> 4 -> 8 -> 2
// 最后的 2 和前面的 2 是同一个节点
这个链表中存在环，并且环的开始节点是 2，于是你要返回节点 2。

相关视频：27. 判断单链表是否有环

代码#

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;
  }

}