Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumfast-slow-pointers

Linked List Cycle II

Problem (restated)

Return the node where the cycle begins, or null.

Intuition

After meet, restart one pointer at head; same pace meets at entrance.

Approaches

Floyd's cycle entry

Tested only

Time O(n)Space O(1)

Idea. Detect cycle with fast/slow; then head and meet walk until equal.

Walkthrough. Cycle starting at node 2: second phase returns that node.

Trade-offs. Hash set of seen nodes is O(n) space.

Solution

export class ListNode {
  val: number; next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}
export function detectCycle(head: ListNode | null): ListNode | null {
  if (!head?.next) return null;
  let slow: ListNode | null = head, fast: ListNode | null = head;
  while (fast?.next) {
    slow = slow!.next; fast = fast.next.next;
    if (slow === fast) {
      let p: ListNode | null = head;
      while (p !== slow) { p = p!.next; slow = slow!.next; }
      return p;
    }
  }
  return null;
}

export class ListNode {
  val: number; next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}
export function detectCycle(head: ListNode | null): ListNode | null {
  if (!head?.next) return null;
  let slow: ListNode | null = head, fast: ListNode | null = head;
  while (fast?.next) {
    slow = slow!.next; fast = fast.next.next;
    if (slow === fast) {
      let p: ListNode | null = head;
      while (p !== slow) { p = p!.next; slow = slow!.next; }
      return p;
    }
  }
  return null;
}

Reflection

Which cue made you pick this pattern in under 90 seconds?
What input would break a wrong invariant?