Đảo ngược một linked list (Reverse Linked List) — trình bày cách iterative và độ phức tạp?

Ý tưởng: Duyệt một lần, lật từng con trỏ next để trỏ ngược lại. Cần 3 biến: prev, curr, và lưu tạm next trước khi ghi đè.

Các bước: giữ next = curr.next (kẻo mất phần đuôi) → curr.next = prev → dời prev = curr, curr = next. Khi curr null thì prev chính là head mới.

Hình dung: như đảo chiều một dãy mũi tên domino — phải nhớ ô kế tiếp trước khi xoay ô hiện tại.

class ListNode { val: number; next: ListNode | null = null; constructor(v: number){ this.val = v } }

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null
  let curr = head
  while (curr) {
    const next = curr.next
    curr.next = prev
    prev = curr
    curr = next
  }
  return prev
}

Độ phức tạp: thời gian O(n), bộ nhớ O(1).

Lưu ý: Bản đệ quy cũng O(n) nhưng tốn O(n) stack — phỏng vấn thường ưu tiên iterative cho an toàn stack overflow.