Linked List
Cấu trúc liên kết

3.1 Linked List là gì?

Linked List (danh sách liên kết) là một chuỗi các node, mỗi node chứa:

• value — dữ liệu
• next — tham chiếu đến node tiếp theo (hoặc null nếu là cuối)

Khác với array, các node không nằm liên tiếp trong RAM — chúng nằm rải rác, kết nối qua reference.

head → [3|·] → [7|·] → [9|·] → [2|·] → null
        node1   node2   node3   node4

Khai báo Node trong JS

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

// Tạo linked list 1 → 2 → 3 thủ công:
const head = new ListNode(1, new ListNode(2, new ListNode(3)));

// Hoặc:
const a = new ListNode(1);
const b = new ListNode(2);
const c = new ListNode(3);
a.next = b;
b.next = c;
// head = a

3.2 Linked List vs Array — đánh đổi

3.3 Singly Linked List — cài đặt đầy đủ

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // O(1) — thêm vào đầu
  prepend(val) {
    const node = new ListNode(val, this.head);
    this.head = node;
    if (!this.tail) this.tail = node;
    this.size++;
  }

  // O(1) — thêm vào cuối (vì lưu tail pointer)
  append(val) {
    const node = new ListNode(val);
    if (!this.head) {
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
  }

  // O(n) — lấy node thứ index
  getNode(index) {
    if (index < 0 || index >= this.size) return null;
    let curr = this.head;
    for (let i = 0; i < index; i++) curr = curr.next;
    return curr;
  }

  // O(n) — chèn vào index
  insertAt(index, val) {
    if (index === 0) return this.prepend(val);
    if (index === this.size) return this.append(val);
    const prev = this.getNode(index - 1);
    if (!prev) throw new Error('Index out of range');
    prev.next = new ListNode(val, prev.next);
    this.size++;
  }

  // O(n) — xoá node thứ index
  removeAt(index) {
    if (index < 0 || index >= this.size) return null;
    let removed;
    if (index === 0) {
      removed = this.head;
      this.head = this.head.next;
      if (!this.head) this.tail = null;
    } else {
      const prev = this.getNode(index - 1);
      removed = prev.next;
      prev.next = removed.next;
      if (removed === this.tail) this.tail = prev;
    }
    this.size--;
    return removed.val;
  }

  // O(n) — chuyển sang array để in
  toArray() {
    const result = [];
    let curr = this.head;
    while (curr) {
      result.push(curr.val);
      curr = curr.next;
    }
    return result;
  }
}

// Demo:
const list = new SinglyLinkedList();
list.append(1);
list.append(2);
list.append(3);
list.prepend(0);
list.insertAt(2, 99);
console.log(list.toArray());  // [0, 1, 99, 2, 3]
list.removeAt(0);
console.log(list.toArray());  // [1, 99, 2, 3]

3.4 Doubly Linked List — duyệt 2 chiều

Mỗi node có thêm prev trỏ về node phía trước.

     ←prev      ←prev      ←prev
[3|·]      [7|·]      [9|·]      [2|·]
     next→      next→      next→

class DListNode {
  constructor(val = 0, prev = null, next = null) {
    this.val = val;
    this.prev = prev;
    this.next = next;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // O(1) — thêm cuối
  append(val) {
    const node = new DListNode(val, this.tail, null);
    if (!this.head) {
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
  }

  // O(1) — xoá node bất kỳ KHI ĐÃ CÓ REFERENCE đến node đó
  removeNode(node) {
    if (node.prev) node.prev.next = node.next;
    else this.head = node.next;

    if (node.next) node.next.prev = node.prev;
    else this.tail = node.prev;

    this.size--;
  }

  // O(1) — chèn sau một node bất kỳ
  insertAfter(node, val) {
    const newNode = new DListNode(val, node, node.next);
    if (node.next) node.next.prev = newNode;
    else this.tail = newNode;
    node.next = newNode;
    this.size++;
  }
}

3.5 Circular Linked List — vòng tròn

Node cuối cùng next trỏ về head thay vì null.

head → [3|·] → [7|·] → [9|·] → [2|·]
        ↑                              │
        └──────────────────────────────┘

Ứng dụng

• Round-robin scheduler: hệ điều hành luân phiên CPU cho process
• Multiplayer game turn: luân phiên lượt chơi
• Music playlist (loop): phát lại từ đầu khi hết
• Buffer ring: producer/consumer với fixed-size buffer

// Phát hiện circular: dùng fast-slow pointer (xem 3.7)
function isCircular(head) {
  if (!head) return false;
  let slow = head, fast = head.next;
  while (fast && fast.next) {
    if (slow === fast) return true;
    slow = slow.next;
    fast = fast.next.next;
  }
  return false;
}

3.6 Dummy Node Pattern — tránh edge case head

Khi xử lý linked list, edge case "node cần xoá là head" thường gây code phức tạp với nhiều if/else. Dummy node (node giả) giải quyết đẹp vấn đề này.

Ví dụ: Remove all elements with value = val

// ❌ Không có dummy — phức tạp với edge case
function removeElementsBad(head, val) {
  // Xử lý head trước
  while (head && head.val === val) head = head.next;
  if (!head) return null;
  let curr = head;
  while (curr.next) {
    if (curr.next.val === val) curr.next = curr.next.next;
    else curr = curr.next;
  }
  return head;
}

// ✅ Có dummy — code thanh lịch
function removeElements(head, val) {
  const dummy = new ListNode(0, head);
  let curr = dummy;
  while (curr.next) {
    if (curr.next.val === val) {
      curr.next = curr.next.next;
    } else {
      curr = curr.next;
    }
  }
  return dummy.next;
}

Dummy node "đứng trước" head, nên ta luôn có prev để thao tác. Cuối cùng trả dummy.next.

3.7 Fast & Slow Pointer — vũ khí chính của Linked List

Ý tưởng: dùng 2 pointer di chuyển trên linked list với tốc độ khác nhau (thường fast=2 bước, slow=1 bước mỗi lần). Nhiều bài kinh điển dùng kỹ thuật này.

3.7.1 Tìm middle node

// Khi fast đến cuối, slow đang ở giữa
function findMiddle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

// 1 → 2 → 3 → 4 → 5 → null
//         ↑
//       middle (3)

// 1 → 2 → 3 → 4 → null
//         ↑
//   middle = 3 (lấy node thứ 2 trong cặp giữa)

3.7.2 Phát hiện cycle (Floyd's Tortoise & Hare)

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Tại sao đúng? Nếu có cycle, fast (chạy nhanh) sẽ "bắt kịp" slow trong vòng tròn. Mỗi vòng, khoảng cách giữa fast và slow giảm 1 → chắc chắn gặp nhau.

3.7.3 Tìm điểm bắt đầu cycle

function detectCycle(head) {
  let slow = head, fast = head;
  // Bước 1: tìm gặp nhau
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      // Bước 2: reset slow về head, đi cùng tốc độ với fast
      slow = head;
      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow;  // điểm vào cycle
    }
  }
  return null;
}

3.7.4 Tìm node thứ k từ cuối

function nthFromEnd(head, k) {
  let fast = head;
  // Đẩy fast đi trước k bước
  for (let i = 0; i < k; i++) {
    if (!fast) return null;
    fast = fast.next;
  }
  // Sau đó cả hai cùng đi đến khi fast hết
  let slow = head;
  while (fast) {
    slow = slow.next;
    fast = fast.next;
  }
  return slow;
}

3.8 Reverse Linked List — phải biết cả iterative và recursive

Iterative — 3 con trỏ

function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr) {
    const next = curr.next;  // lưu lại next
    curr.next = prev;        // đảo hướng
    prev = curr;
    curr = next;
  }
  return prev;  // prev là head mới
}

// Demo từng bước với 1 → 2 → 3 → null:
// Init: prev=null, curr=1
// Bước 1: next=2, 1.next=null, prev=1, curr=2
//   → null ← 1     2 → 3
// Bước 2: next=3, 2.next=1, prev=2, curr=3
//   → null ← 1 ← 2     3
// Bước 3: next=null, 3.next=2, prev=3, curr=null
//   → null ← 1 ← 2 ← 3
// Return prev = 3

Recursive — đẹp nhưng khó hiểu

function reverseListRec(head) {
  if (!head || !head.next) return head;
  const newHead = reverseListRec(head.next);
  head.next.next = head;  // đảo hướng
  head.next = null;
  return newHead;
}

// Demo với 1 → 2 → 3:
// reverseListRec(1):
//   reverseListRec(2):
//     reverseListRec(3) → return 3 (base case)
//     [tại đây list là: 1 → 2 → 3]
//     2.next.next = 2  // tức 3.next = 2
//     2.next = null
//     [list giờ: 1 → 2 ← 3, 2 không có next]
//     return 3
//   1.next.next = 1  // tức 2.next = 1
//   1.next = null
//   return 3
// Final: 3 → 2 → 1

Reverse một đoạn (m đến n)

function reverseBetween(head, m, n) {
  const dummy = new ListNode(0, head);
  let prev = dummy;
  for (let i = 1; i < m; i++) prev = prev.next;
  // prev đứng ngay trước node thứ m

  let curr = prev.next;
  for (let i = 0; i < n - m; i++) {
    const next = curr.next;
    curr.next = next.next;
    next.next = prev.next;
    prev.next = next;
  }
  return dummy.next;
}

3.9 Merge & Sort Linked List

3.9.1 Merge Two Sorted Lists

function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }
  tail.next = l1 || l2;  // gắn phần còn lại
  return dummy.next;
}

3.9.2 Merge Sort cho Linked List — O(n log n)

Khác với array (thường dùng quick sort), linked list dùng merge sort vì:

• Quick sort cần truy cập ngẫu nhiên cho pivot → linked list không có
• Merge sort không cần extra space khi merge hai linked list

function sortList(head) {
  if (!head || !head.next) return head;

  // 1. Tìm giữa và chia đôi
  let slow = head, fast = head, prev = null;
  while (fast && fast.next) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }
  prev.next = null;  // ngắt đôi

  // 2. Đệ quy sort 2 nửa
  const left  = sortList(head);
  const right = sortList(slow);

  // 3. Merge
  return mergeTwoLists(left, right);
}

3.9.3 Merge K Sorted Lists — O(n log k) với heap

// Dùng min-heap chứa head của k list
// Mỗi lần lấy node nhỏ nhất, push next của nó vào heap
// Heap sẽ học chi tiết ở Chương 10

// Phiên bản đơn giản dùng divide & conquer:
function mergeKLists(lists) {
  if (lists.length === 0) return null;
  while (lists.length > 1) {
    const merged = [];
    for (let i = 0; i < lists.length; i += 2) {
      const l1 = lists[i];
      const l2 = i + 1 < lists.length ? lists[i + 1] : null;
      merged.push(mergeTwoLists(l1, l2));
    }
    lists = merged;
  }
  return lists[0];
}
// Big-O: O(n log k) — log k tầng, mỗi tầng tổng cộng O(n)

Bài tập

1 → 2 → 3 → 4 → 5, n = 2 → 1 → 2 → 3 → 5

(2 → 4 → 3) + (5 → 6 → 4)
biểu diễn 342 + 465 = 807
→ (7 → 0 → 8)

Tổng kết chương 3

• ✅ Linked list = chuỗi node nối qua pointer; truy cập index O(n) nhưng chèn/xoá O(1) khi đã có pointer
• ✅ Doubly LL cho phép xoá node bất kỳ O(1) — nền cho LRU Cache
• ✅ Dummy node giúp tránh edge case head, code thanh lịch hơn
• ✅ Fast & Slow pointer: tìm middle, phát hiện cycle, tìm node thứ k từ cuối
• ✅ Floyd's algorithm phát hiện và tìm điểm vào cycle với O(1) space
• ✅ Reverse: cả iterative (3 con trỏ) và recursive — biết cả hai
• ✅ Linked list dùng merge sort, không phải quick sort