Bài toán
Cho đầu (head) của một danh sách liên kết đơn (Singly Linked List). Hãy đảo ngược danh sách và trả về head mới.
Ví dụ:
text:
Input: 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 5 -> 4 -> 3 -> 2 -> 1 -> nullPhân Tích & Tiếp Cận
Iterative (Vòng lặp) - O(1) Space
Tại mỗi bước, ta đang đứng ở node curr. Ta muốn đổi hướng mũi tên của nó trỏ ngược về prev.
Nhưng nếu ta đổi hướng ngay (curr.next = prev), ta sẽ làm đứt dây xích và mất dấu node tiếp theo (next).
Vì vậy, ta cần lưu next vào một biến tạm trước khi đổi hướng.
Quy trình 3 bước tại mỗi node:
- Lưu
next:temp = curr.next. - Đảo chiều:
curr.next = prev. - Tiến lên:
prev = curr,curr = temp.
typescript:
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let curr: ListNode | null = head;
while (curr !== null) {
const nextTemp = curr.next; // Lưu tham chiếu người tiếp theo
curr.next = prev; // Đảo chiều mũi tên
prev = curr; // Tiến prev lên
curr = nextTemp; // Tiến curr lên
}
return prev; // Khi vòng lặp kết thúc, curr là null, prev chính là head mới
}- Time Complexity: $O(n)$ - Duyệt mỗi node 1 lần.
- Space Complexity: $O(1)$.
Recursive (Đệ quy) - O(n) Space
Tư duy đệ quy: "Hãy đảo ngược phần còn lại của danh sách (từ node thứ 2 trở đi), sau đó nối node đầu hiện tại vào cuối danh sách đã đảo ngược đó."
typescript:
function reverseList(head: ListNode | null): ListNode | null {
// Base case: Danh sách rỗng hoặc chỉ có 1 node
if (!head || !head.next) {
return head;
}
// Đệ quy: Đảo ngược phần đuôi
const newHead = reverseList(head.next);
// Nối ngược lại: Node tiếp theo (head.next) giờ phải trỏ về mình (head)
head.next.next = head;
head.next = null; // Cắt đuôi cũ để tránh vòng lặp vô hạn
return newHead;
}- Space Complexity: $O(n)$ do Call Stack.
Ứng dụng thực tế
Việc thao tác con trỏ (references) là kỹ năng cốt lõi khi làm việc với các cấu trúc dữ liệu phức tạp dạng Graph, Tree, hoặc thậm chí là quản lý State object lồng nhau trong Redux/React.