Reorder List: ba thao tác bạn đã biết

[1, 2, 3, 4, 5] trở thành [1, 5, 2, 4, 3]. Đầu và đuôi được kéo xen vào nhau. Lúc đầu nhìn vào bài này tôi bắt đầu phác thảo một cách tiếp cận tùy biến — một vũ điệu in-place nào đó sẽ thăm các node theo đúng thứ tự. Khoảng ba phút sau tôi dừng lại. Hình dạng của output quen thuộc: phần trước xen kẽ với phần sau. Tôi đã thấy pattern đó trước đây, chỉ là không phải trong bối cảnh linked list.

Cấu trúc thực sự của bài toán là: lấy nửa đầu nguyên vẹn, lấy nửa sau đã đảo ngược, sau đó xen kẽ chúng. Khi nhận ra điều đó, thuật toán tự viết ra. Ba thao tác, mỗi cái đã được giải quyết rồi.

Constraints đang nói gì

List có tối đa 50,000 node. Giá trị node từ 1 đến 1000 — không liên quan ở đây, vì bạn không sort hay so sánh giá trị, chỉ sắp xếp lại pointer. Ràng buộc thực sự quan trọng là "không được thay đổi giá trị trong node, chỉ được thay đổi bản thân node." Điều đó loại trừ mẹo hoán đổi giá trị và buộc bạn phải rewire lại các liên kết.

50,000 node có nghĩa là O(n²) khá nguy hiểm. Một cách tiếp cận liên tục đi đến tail và splice nó vào sẽ tốn khoảng 2.5 tỷ thao tác pointer. Giới hạn thực tế ở đây là O(n).

Điều constraints còn tiết lộ: bạn cần truy cập đồng thời vào cả hai đầu của list. Array cho bạn điều đó miễn phí qua index. Linked list thì không — bạn không thể nhảy thẳng tới index n - 1 mà không đi bộ tới đó. Sức căng đó chính là toàn bộ bài toán. Hoặc bạn chấp nhận O(n) auxiliary space để có random access, hoặc bạn tìm cách cấu trúc lại list để cả hai đầu tự đến với bạn.

Brute force: thu thập vào array, rewire bằng two pointers

Con đường trực tiếp nhất: đổ tất cả các node vào array, rồi dùng two pointers để rewire lại. Left bắt đầu ở 0, right ở n - 1. Mỗi vòng lặp: kết nối left với right, tiến left; kết nối right với left mới, lùi right. Dừng khi hai pointer gặp nhau.

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head or not head.next:
            return
 
        nodes = []
        cur = head
        while cur:
            nodes.append(cur)
            cur = cur.next
 
        left, right = 0, len(nodes) - 1
        while left < right:
            nodes[left].next = nodes[right]
            left += 1
            if left == right:
                break
            nodes[right].next = nodes[left]
            right -= 1
 
        nodes[left].next = None

public class Solution {
    public void ReorderList(ListNode head) {
        if (head == null || head.next == null) return;
 
        var nodes = new List<ListNode>();
        var cur = head;
        while (cur != null) {
            nodes.Add(cur);
            cur = cur.next;
        }
 
        int left = 0, right = nodes.Count - 1;
        while (left < right) {
            nodes[left].next = nodes[right];
            left++;
            if (left == right) break;
            nodes[right].next = nodes[left];
            right--;
        }
 
        nodes[left].next = null;
    }
}

Trace qua [1, 2, 3, 4]. Sau khi thu thập, nodes = [1, 2, 3, 4], left = 0, right = 3.

Vòng 1: nodes[0].next = nodes[3] — node 1 trỏ tới node 4. Tiến left lên 1. left != right, tiếp tục. nodes[3].next = nodes[1] — node 4 trỏ tới node 2. Lùi right xuống 2.

Vòng 2: nodes[1].next = nodes[2] — node 2 trỏ tới node 3. Tiến left lên 2. Bây giờ left == right, break.

Sau vòng lặp: nodes[2].next = None — node 3 trỏ tới null.

Chuỗi: 1 -> 4 -> 2 -> 3 -> null. Đúng.

if left == right: break bên trong vòng lặp xử lý trường hợp độ dài lẻ. Sau nodes[left].next = nodes[right] bạn tiến left trước khi kiểm tra điều kiện kết thúc, vì với list độ dài lẻ hai pointer hội tụ trên cùng một node — node đó phải trỏ đến null, không trỏ vào chính nó.

O(n) time, O(n) space. Với n = 50,000 thì space vẫn ổn — chỉ vài trăm KB pointer. Nhưng có phiên bản O(1) space, và đáng biết vì nó xâu chuỗi chính xác những primitive mà series linked list này đang xây dựng.

Cách O(1): phân tách thành ba bài toán quen thuộc

Sự phân tách:

1. Tìm điểm giữa của list (slow/fast pointers).
2. Đảo ngược nửa sau — đây là LeetCode 206 y chang.
3. Merge xen kẽ từ nửa đầu và nửa sau đã đảo ngược.

Trạng thái của [1, 2, 3, 4, 5] ở từng giai đoạn:

Mỗi bước là bài toán độc lập. Không bước nào cần bước kia để hoạt động. Tính composability này chính là điểm mấu chốt — và đó là lý do code dưới đây đọc gần như là lắp ghép ba hàm đã giải trước đó.

Bước 1: slow/fast pointers để tìm điểm giữa

Nếu bạn đã làm Middle of the Linked List (876), đây là y chang. slow di chuyển một bước; fast di chuyển hai bước. Khi fast hết chỗ đi, slow đang ở điểm giữa.

Điều kiện kết thúc là while fast.next and fast.next.next. Cái này dừng slow tại node cuối cùng của nửa đầu, không phải node đầu tiên của nửa sau. Với [1, 2, 3, 4]: slow dừng ở 2, và slow.next (là 3) trở thành head của nửa sau. Với [1, 2, 3, 4, 5]: slow dừng ở 3, và slow.next (node 4) bắt đầu nửa sau.

slow, fast = head, head
while fast.next and fast.next.next:
    slow = slow.next
    fast = fast.next.next
 
second = slow.next
slow.next = None  # cắt đứt nửa đầu

Đừng bỏ qua bước cắt đứt. Không có slow.next = None, nửa đầu vẫn trỏ vào nửa sau. Bước merge sau đó sẽ tạo ra một cycle.

Điều kiện sai là while fast and fast.next. Với list 5 node, cái đó dừng slow ở node 3 thay vì node 2, và nửa sau bắt đầu từ node 4, mất node 3.

Trace vị trí pointer cho [1, 2, 3, 4, 5] từng bước:

Bước 2: đảo ngược nửa sau

Đúng code từ Reverse Linked List (206):

prev = None
cur = second
while cur:
    nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt
second = prev

prev bắt đầu ở None vì tail mới phải trỏ đến null. Sau vòng lặp, prev là head mới của đoạn đã đảo ngược.

Với [4, 5], trace:

Trạng thái ban đầu: prev=None, cur=4, 4->5->null

Vòng 1: nxt=5, 4.next=None, prev=4, cur=5. Bây giờ 4->null.

Vòng 2: nxt=None, 5.next=4, prev=5, cur=None. Bây giờ 5->4->null.

Vòng lặp kết thúc. second = prev = 5. Nửa sau đã đảo ngược là 5 -> 4 -> null.

ListNode prev = null, cur = second;
while (cur != null) {
    ListNode nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
}
second = prev;

Bước 3: merge xen kẽ

Cả hai nửa đều kết thúc bằng null. Việc merge:

first = head
while second:
    tmp1 = first.next
    tmp2 = second.next
 
    first.next = second
    second.next = tmp1
 
    first = tmp1
    second = tmp2

Một vòng lặp: lưu first.next và second.next gốc trước khi ghi đè bất cứ thứ gì, gắn second sau first, gắn first.next đã lưu sau second, rồi tiến cả hai pointer.

Trace đầy đủ cho [1, 2, 3] (nửa đầu) và [5, 4] (nửa sau đã đảo ngược, từ input 5 node):

Trước vòng lặp: first=1, second=5. Chuỗi: 1->2->3->null, 5->4->null.

Sau vòng 1: 1 -> 5 -> 2 -> 3 -> null và 4 -> null. first = 2, second = 4.

Sau vòng 2: 1 -> 5 -> 2 -> 4 -> 3 -> null. second = null. Vòng lặp kết thúc.

Nửa sau kết thúc vòng lặp vì sau khi chia, nửa sau bằng hoặc ngắn hơn một node so với nửa đầu. Nửa đầu luôn có node sẵn khi nửa sau vẫn còn.

ListNode first = head;
while (second != null) {
    ListNode tmp1 = first.next;
    ListNode tmp2 = second.next;
    first.next = second;
    second.next = tmp1;
    first = tmp1;
    second = tmp2;
}

Giải pháp O(1) space hoàn chỉnh

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head or not head.next:
            return
 
        # Bước 1: tìm điểm giữa
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
 
        # Bước 2: đảo ngược nửa sau
        second = slow.next
        slow.next = None
        prev = None
        cur = second
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        second = prev
 
        # Bước 3: merge xen kẽ
        first = head
        while second:
            tmp1 = first.next
            tmp2 = second.next
            first.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2

public class Solution {
    public void ReorderList(ListNode head) {
        if (head == null || head.next == null) return;
 
        // Bước 1: tìm điểm giữa
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
 
        // Bước 2: đảo ngược nửa sau
        ListNode second = slow.next;
        slow.next = null;
        ListNode prev = null, cur = second;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        second = prev;
 
        // Bước 3: merge xen kẽ
        ListNode first = head;
        while (second != null) {
            ListNode tmp1 = first.next;
            ListNode tmp2 = second.next;
            first.next = second;
            second.next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
}

O(n) time — mỗi trong ba lần duyệt chạm mỗi node tối đa một lần. O(1) extra space — chỉ các biến pointer.

So sánh hai cách tiếp cận

Cùng time, space khác nhau. Phiên bản ba bước không nhanh hơn — nó tốt hơn ở chỗ không cần bộ nhớ tỉ lệ với input, và nó luyện tập ba primitive của linked list xuất hiện liên tục trong các bài khác.

Tôi sẽ dùng phiên bản ba bước trong bất kỳ code review nào. Cách array ổn như bản nháp đầu tiên trên bảng trắng; tôi sẽ flag ngay nếu ai đó cố gắng merge nó vào production.

Edge cases và tại sao code xử lý được

1 hoặc 2 node. Guard if not head or not head.next: return bắt cả hai. Một node không có gì để reorder; hai node đã đúng thứ tự rồi (L0 -> L1 chính là L0 -> Ln).

3 node [1, 2, 3]. Slow dừng ở 2. Nửa sau là [3], đảo ngược vẫn là [3]. Merge chạy một lần: 1 -> 3, rồi 3.next = 2. second thành null, vòng kết thúc. Kết quả: 1 -> 3 -> 2 -> null. Node giữa kết thúc ở tail.

4 node [1, 2, 3, 4] (chẵn). Slow dừng ở 2. Nửa sau [3, 4] đảo ngược thành [4, 3]. Cả hai nửa dài 2. Vòng merge chạy đúng hai lần rồi kết thúc khi second hết. Kết quả: 1 -> 4 -> 2 -> 3.

5 node [1, 2, 3, 4, 5] (lẻ). Slow dừng ở 3. Nửa sau [4, 5] đảo ngược thành [5, 4]. Nửa đầu có 3 node, nửa sau có 2. Vòng merge chạy hai lần, rồi second là null. Node 3 ở lại là tail của nửa đầu và kết thúc ở cuối. Kết quả: 1 -> 5 -> 2 -> 4 -> 3.

Thiếu bước cắt đứt (slow.next = None). Nếu bỏ dòng này, nửa đầu vẫn có 3 -> 4 -> 5 gắn theo. Bước merge sau đó chạy vào các node thừa đó, tạo list bị corrupt hoặc vòng lặp vô tận tùy theo thứ tự pointer bị ghi đè. Bước cắt đứt không phải tùy chọn.

Sai điều kiện slow/fast (while fast and fast.next). Trên [1, 2, 3, 4, 5], điều kiện này cho slow đến node 3 (điểm giữa thực sự), vì vậy nửa sau bắt đầu từ node 4, mất node 3 khỏi nửa sau. Điều kiện while fast.next and fast.next.next mới là điều kiện chính xác.

Pattern ẩn sau bài này

Bài toán này là sự kết hợp của ba primitive chuẩn của linked list: phát hiện điểm giữa (rùa và thỏ), đảo ngược in-place, và merge xen kẽ. Không primitive nào được phát minh ở đây; chúng tồn tại như các bài LeetCode độc lập. Insight mở khóa Reorder List là nhận ra rằng thao tác bạn muốn — zip phần trước với phần sau đã đảo ngược — chính xác là sự kết hợp của ba cái đó.

Tính composability đó là thứ phân biệt cách tiếp cận của kỹ sư có kinh nghiệm với người mới. Người mới cố tìm một vòng lặp khéo léo duy nhất. Kỹ sư có kinh nghiệm hỏi: bài này có thể phân tách không? Và nếu có, nó phân tách thành những primitive nào?

Vị trí của bài trong series linked list

Bài này yêu cầu thành thạo Reverse Linked List (206) — Bước 2 chính là bài đó. Nếu logic đảo ngược cảm thấy chậm khi viết, luyện 206 trước.

Middle of the Linked List (876) là Bước 1. Điều kiện kết thúc while fast.next and fast.next.next không phải tùy ý; nó đến từ đó.

Merge Two Sorted Lists (21) có cấu trúc tương tự Bước 3: lưu cả hai next pointer, rewire, tiến. Sự khác biệt duy nhất là merge dùng so sánh giá trị còn Bước 3 xen kẽ vô điều kiện.

Palindrome Linked List (234) xâu chuỗi Bước 1 và 2 của bài này — tìm điểm giữa, đảo ngược nửa sau — rồi so sánh hai nửa theo giá trị. Đây là bài sibling gần nhất: setup giống, bước cuối khác.

Sort List (148) về cơ bản áp dụng cấu trúc của bài này đệ quy. Việc chia tại điểm giữa trở thành bước divide của merge sort; bước merge trở thành merge hai nửa đã sắp xếp. Nếu Bước 1 và 3 ở đây đã tự nhiên, Sort List là bài tiếp theo nên làm.

Reverse Nodes in k-Group (25) tổng quát hóa Bước 2: thay vì đảo ngược nửa sau một lần, bạn đảo ngược mỗi nhóm k node liên tiếp trong toàn bộ list. Logic pointer manipulation là cùng một lockstep ba biến.