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

Middle of the Linked List

Problem (restated)

Given the head of a singly linked list, return the middle node. If two middles, return the second.

Intuition

Slow moves one step, fast two; when fast finishes, slow is at the middle.

Approaches

Fast & slow pointers

Tested only

Time O(n)Space O(1)

Idea. Advance until fast is null or fast.next is null; return slow.

Walkthrough. 1→2→3→4→5 → slow ends on 3; even length ends on second middle.

Trade-offs. Counting length first is two passes; this is one pass O(1) 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 middleNode(head: ListNode | null): ListNode | null {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow;
}

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

Reflection

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