Bài viết này khám phá các giải pháp cho một số vấn đề thường gặp khi làm việc với danh sách liên kết, bao gồm việc hoán đổi các cặp nút liền kề, loại bỏ nút thứ N từ cuối danh sách và xác định điểm giao nhau của hai danh sách. Mỗi giải pháp đều được trình bày kèm theo phân tích và mã nguồn minh họa.

Hoán Đổi Cặp Nút Trong Danh Sách Liên Kết (LeetCode 24)

Bài toán yêu cầu hoán đổi vị trí của mỗi cặp nút kề nhau trong một danh sách liên kết. Ví dụ, nếu danh sách là 1->2->3->4, kết quả mong muốn là 2->1->4->3.

Để giải quyết bài toán này một cách hiệu quả, chúng ta có thể sử dụng một nút giả (dummy node) ở đầu danh sách. Nút giả giúp đơn giản hóa việc xử lý các trường hợp cạnh, đặc biệt khi hoán đổi cặp nút đầu tiên của danh sách. Chúng ta sẽ lặp qua danh sách, tại mỗi bước, xác định hai nút cần hoán đổi và sau đó điều chỉnh các con trỏ liên kết.

Giải pháp lặp

Chúng ta khởi tạo một nút giả headSentinel trỏ đến nút đầu tiên của danh sách gốc. Một con trỏ current sẽ được dùng để duyệt và điều chỉnh liên kết. Trong mỗi lần lặp, chúng ta kiểm tra xem có đủ hai nút kế tiếp (current.next và current.next.next) để thực hiện hoán đổi hay không. Nếu có, chúng ta lưu lại các nút này và nút tiếp theo sau cặp đó, sau đó thực hiện ba bước điều chỉnh con trỏ để đảo ngược thứ tự của cặp nút.

1. Trỏ current.next đến nút thứ hai của cặp.
2. Trỏ nút thứ hai đến nút thứ nhất.
3. Trỏ nút thứ nhất đến phần còn lại của danh sách (nút sau cặp đã hoán đổi).

Sau khi hoán đổi, con trỏ current sẽ được di chuyển đến nút thứ nhất (hiện đang ở vị trí thứ hai trong cặp) để chuẩn bị cho lần lặp tiếp theo.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode headSentinel = new ListNode(0); // Nút giả để đơn giản hóa việc xử lý đầu danh sách
        headSentinel.next = head;
        ListNode current = headSentinel;

        while (current.next != null && current.next.next != null) {
            ListNode firstNode = current.next;
            ListNode secondNode = current.next.next;
            ListNode restOfList = secondNode.next;

            // Bước 1: Điều chỉnh liên kết từ nút hiện tại đến nút thứ hai
            current.next = secondNode;
            // Bước 2: Điều chỉnh liên kết của nút thứ hai đến nút thứ nhất
            secondNode.next = firstNode;
            // Bước 3: Điều chỉnh liên kết của nút thứ nhất đến phần còn lại của danh sách
            firstNode.next = restOfList;

            // Di chuyển con trỏ 'current' đến nút thứ nhất (sau khi hoán đổi nó là nút cuối của cặp mới)
            current = firstNode;
        }

        return headSentinel.next;
    }
}

Xóa Nút Thứ N Từ Cuối Danh Sách Liên Kết (LeetCode 19)

Yêu cầu của bài toán là loại bỏ nút thứ N tính từ cuối của một danh sách liên kết và trả về đầu danh sách. Ví dụ, nếu danh sách là 1->2->3->4->5 và N=2, chúng ta cần xóa nút '4', kết quả là 1->2->3->5.

Phương pháp hiệu quả nhất để giải quyết bài toán này là sử dụng hai con trỏ, thường được gọi là con trỏ nhanh (fast pointer) và con trỏ chậm (slow pointer). Cả hai con trỏ đều bắt đầu từ một nút giả trỏ đến đầu danh sách gốc để đơn giản hóa việc xóa nút đầu tiên nếu cần.

Giải pháp Hai Con Trỏ

1. Khởi tạo một nút giả sentinel trỏ đến head.
2. Khởi tạo hai con trỏ: slowPtr và fastPtr, cả hai đều bắt đầu từ sentinel.
3. Di chuyển fastPtr về phía trước n bước. Điều này tạo ra một khoảng cách n nút giữa fastPtr và slowPtr.
4. Di chuyển cả slowPtr và fastPtr về phía trước cùng một lúc, mỗi lần một bước, cho đến khi fastPtr đến cuối danh sách (tức là fastPtr.next == null).
5. Khi fastPtr đến cuối, slowPtr sẽ nằm ở vị trí ngay trước nút cần xóa. Lúc này, chỉ cần cập nhật con trỏ next của slowPtr để bỏ qua nút cần xóa.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode(0); // Nút giả
        sentinel.next = head;

        ListNode slowPtr = sentinel;
        ListNode fastPtr = sentinel;

        // Di chuyển fastPtr trước n bước
        for (int i = 0; i < n; i++) {
            if (fastPtr == null) { // Đảm bảo n không lớn hơn kích thước danh sách
                return head;
            }
            fastPtr = fastPtr.next;
        }

        // Di chuyển cả slowPtr và fastPtr cho đến khi fastPtr đến cuối danh sách
        // Khi đó slowPtr sẽ ở ngay trước nút cần xóa
        while (fastPtr.next != null) {
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next;
        }

        // Bỏ qua nút cần xóa
        slowPtr.next = slowPtr.next.next;

        return sentinel.next; // Trả về đầu danh sách đã sửa đổi
    }
}

Tìm Điểm Giao Nhau Của Hai Danh Sách Liên Kết (LeetCode Miệng 02.07)

Bài toán này yêu cầu tìm nút mà tại đó hai danh sách liên kết độc lập bắt đầu giao nhau. Nếu không có điểm giao nhau, trả về null.

Một phương pháp thông minh để giải quyết vấn đề này là sử dụng hai con trỏ di chuyển qua cả hai danh sách. Ý tưởng chính là nếu hai danh sách giao nhau, chúng sẽ có cùng một phần đuôi chung. Nếu chúng ta làm cho cả hai con trỏ đi qua cùng một tổng số nút, chúng sẽ gặp nhau tại điểm giao nhau hoặc tại null nếu không có giao nhau.

Giải pháp Hai Con Trỏ Gặp Nhau

1. Khởi tạo hai con trỏ, walkerA và walkerB, lần lượt trỏ đến headA và headB.
2. Trong một vòng lặp, di chuyển cả walkerA và walkerB về phía trước.
3. Nếu walkerA đến cuối danh sách của nó (tức là null), hãy gán lại nó bằng headB. Tương tự, nếu walkerB đến cuối danh sách của nó, hãy gán lại nó bằng headA.
4. Quá trình này tiếp tục cho đến khi walkerA == walkerB. Điểm gặp nhau này chính là nút giao nhau. Nếu không có giao nhau, cả hai con trỏ cuối cùng sẽ cùng đến null và vòng lặp kết thúc, chúng ta trả về null.

Bằng cách này, mỗi con trỏ sẽ đi qua tổng số nút tương đương với độ dài A + độ dài B. Nếu có giao nhau, chúng chắc chắn sẽ gặp nhau tại nút giao nhau. Nếu không có, chúng sẽ cùng gặp nhau tại null sau khi hoàn thành chu trình đi qua cả hai danh sách.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode walkerA = headA;
        ListNode walkerB = headB;

        // Loop cho đến khi cả hai con trỏ gặp nhau
        // Nếu có giao nhau, chúng sẽ gặp nhau tại nút giao
        // Nếu không có giao nhau, chúng sẽ cùng gặp nhau tại null
        while (walkerA != walkerB) {
            // Nếu walkerA đến cuối, di chuyển nó đến đầu danh sách B. Ngược lại, di chuyển nó bình thường.
            walkerA = (walkerA == null) ? headB : walkerA.next;

            // Nếu walkerB đến cuối, di chuyển nó đến đầu danh sách A. Ngược lại, di chuyển nó bình thường.
            walkerB = (walkerB == null) ? headA : walkerB.next;
        }

        return walkerA; // Trả về nút giao nhau (hoặc null nếu không có)
    }
}

Tìm Điểm Bắt Đầu Chu Trình Trong Danh Sách Liên Kết (LeetCode 142)

Bài toán yêu cầu tìm nút bắt đầu của một chu trình trong danh sách liên kết. Nếu không có chu trình, trả về null.

Đây là một vấn đề cổ điển được giải quyết bằng thuật toán của Floyd (còn gọi là thuật toán Tortoise và Hare - Rùa và Thỏ). Thuật toán này bao gồm hai giai đoạn.

Thuật toán Floyd về Chu trình trong Danh sách Liên kết

1. Giai đoạn 1: Phát hiện chu trình.

   Sử dụng hai con trỏ, một con trỏ chậm (tortoise) di chuyển một bước tại mỗi lần lặp và một con trỏ nhanh (hare) di chuyển hai bước. Nếu có chu trình, hai con trỏ này chắc chắn sẽ gặp nhau tại một điểm nào đó bên trong chu trình.

2. Giai đoạn 2: Tìm điểm bắt đầu chu trình.

   Sau khi phát hiện chu trình (hai con trỏ gặp nhau), di chuyển một trong các con trỏ (ví dụ: tortoise) trở lại đầu danh sách (head). Giữ nguyên con trỏ còn lại (hare) tại điểm gặp nhau. Sau đó, di chuyển cả hai con trỏ (tortoise và hare) về phía trước từng bước một. Điểm mà chúng gặp nhau lần thứ hai chính là nút bắt đầu của chu trình.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null; // Không có chu trình nếu danh sách rỗng hoặc chỉ có một nút
        }

        ListNode tortoise = head;
        ListNode hare = head;

        // Giai đoạn 1: Phát hiện chu trình
        // Di chuyển tortoise 1 bước, hare 2 bước
        while (hare != null && hare.next != null) {
            tortoise = tortoise.next;
            hare = hare.next.next;

            if (tortoise == hare) {
                // Chu trình đã được phát hiện
                break;
            }
        }

        // Nếu hare là null hoặc hare.next là null, không có chu trình
        if (hare == null || hare.next == null) {
            return null;
        }

        // Giai đoạn 2: Tìm điểm bắt đầu chu trình
        // Di chuyển tortoise về đầu danh sách
        ListNode entryPoint = head;
        while (entryPoint != tortoise) {
            entryPoint = entryPoint.next;
            tortoise = tortoise.next;
        }

        return entryPoint; // Trả về nút bắt đầu của chu trình
    }
}