Đảo Ngược Danh Sách Liên KếtReverse Linked List
Hiểu bài
Cho head của một danh sách liên kết (linked list) đơn.
Đảo ngược thứ tự các node và trả về head mới.
class ListNode {
val: number
next: ListNode | null
constructor(val: number, next: ListNode | null = null) {
this.val = val
this.next = next
}
}
// Input: 1 → 2 → 3 → null
// Output: 3 → 2 → 1 → nullMấu chốt: mỗi node hiện đang trỏ tới node sau, ta cần cho nó trỏ ngược lại node trước.
Phải lưu next lại trước khi đổi, nếu không sẽ mất phần còn lại của danh sách.
Xem cách cơ bản (chậm hơn)
O(n) time, O(n) spacefunction reverseListExtraSpace(head: ListNode | null): ListNode | null {
const vals: number[] = []
for (let node = head; node; node = node.next) vals.push(node.val)
// Ghi đè giá trị theo thứ tự đảo ngược
let i = vals.length - 1
for (let node = head; node; node = node.next) node.val = vals[i--]
return head
}Cách này mượn một mảng phụ để chứa toàn bộ giá trị rồi ghi đè ngược lại.
Tốn O(n) bộ nhớ thừa, trong khi chỉ cần đảo con trỏ tại chỗ là đủ.
Lời giải tối ưu
O(n) time, O(1) spacefunction reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null
let curr = head
while (curr) {
const nextNode = curr.next // lưu next TRƯỚC khi đổi liên kết
curr.next = prev // đảo con trỏ về phía trước
prev = curr // tiến prev
curr = nextNode // tiến curr
}
return prev // prev dừng ở node cuối — là head mới
}Duyệt một lần, mỗi node đổi next từ trỏ-sau thành trỏ-trước.
- Ba biến
prev,curr,nextNodeđủ để không mất chuỗi. - Vì chỉ đảo con trỏ chứ không tạo node mới nên bộ nhớ phụ O(1) — đây là cách tối ưu, tốt hơn cách dùng mảng.
Chạy thử từng bước
- 1
Khởi tạo prev=null, curr=node(1).
prev:nullcurr:1 - 2
nextNode=2; 1.next=null; prev=1; curr=2.
Chuỗi đảo: 1→null.
prev:1curr:2reversed:"1→null" - 3
nextNode=3; 2.next=1; prev=2; curr=3.
Chuỗi đảo: 2→1→null.
prev:2curr:3reversed:"2→1→null" - 4
nextNode=null; 3.next=2; prev=3; curr=null.
Chuỗi đảo: 3→2→1→null.
prev:3curr:nullreversed:"3→2→1→null" - 5
curr=null, dừng vòng lặp.
Trả về prev=node(3) là head mới.
result:3
Trường hợp biên phải nhớ
head = null (danh sách rỗng) → vòng lặp không chạy → trả về null.
Một node duy nhất → next vốn là null → trả về chính node đó.
Hai node 1→2 → sau khi đảo thành 2→1, đúng.
Phải lưu next trước khi gán curr.next=prev, nếu không sẽ đứt chuỗi.