Đảo đổi từng cặp nút kề nhau (LeetCode 24)

Bài toán yêu cầu hoán đổi vị trí của các nút liền kề trong danh sách liên kết mà không được thay đổi giá trị dữ liệu bên trong nút. Kỹ thuật đệ quy đặc biệt phù hợp cho trường hợp này vì sau khi xử lý cặp nút đầu tiên, phần còn lại của danh sách vẫn giữ nguyên cấu trúc bài toán gốc. Hàm đệ quy sẽ tự động giải quyết các cặp tiếp theo, và khi quay lại (unwind), ta chỉ cần cập nhật lại các con trỏ `next` để nối các đoạn lại.

class Solution {
public:
    ListNode* swapPairs(ListNode* start) {
        if (!start || !start->next) {
            return start;
        }
        ListNode* first = start;
        ListNode* second = start->next;
        first->next = swapPairs(second->next);
        second->next = first;
        return second;
    }
};

Xóa nút thứ n tính từ cuối danh sách (LeetCode 19)

Do danh sách liên kết không hỗ trợ truy cập ngẫu nhiên, việc xác định vị trí nút cần xóa từ cuối đòi hỏi phải biết được nút liền trước nó. Thay vì duyệt hai lần, ta có thể áp dụng chiến lược hai con trỏ cách nhau đúng `n + 1` bước. Con trỏ dẫn đường sẽ đi trước, khi nó chạm đến nút cuối cùng, con trỏ phía sau sẽ tự động dừng lại ngay trước vị trí mục tiêu, cho phép thực hiện thao tác xóa chỉ trong một lần duyệt.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* root, int n) {
        ListNode* lead = root;
        for (int i = 0; i < n; ++i) {
            lead = lead->next;
        }
        if (!lead) {
            return root->next;
        }
        ListNode* trail = root;
        while (lead->next) {
            lead = lead->next;
            trail = trail->next;
        }
        ListNode* target = trail->next;
        trail->next = target->next;
        delete target;
        return root;
    }
};

Tìm điểm giao nhau của hai danh sách liên kết (Interview 02.07)

Khi hai danh sách liên kết giao nhau, chúng sẽ chia sẻ cùng một đoạn đuôi từ điểm giao trở đi. Thách thức chính nằm ở việc hai danh sách có thể có độ dài phần đầu khác nhau. Giải pháp tối ưu là đo chiều dài ban đầu của cả hai, sau đó di chuyển con trỏ của danh sách dài hơn tiến về trước một số bước bằng đúng độ chênh lệch. Khi hai con trỏ thẳng hàng, việc duyệt song song sẽ giúp tìm ra nút trùng khớp đầu tiên, nếu có.

class Solution {
private:
    int measureLength(ListNode* node) {
        int count = 0;
        while (node) {
            node = node->next;
            ++count;
        }
        return count;
    }
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        int lenA = measureLength(headA);
        int lenB = measureLength(headB);
        ListNode* ptrA = headA;
        ListNode* ptrB = headB;
        while (lenA > lenB) {
            ptrA = ptrA->next;
            --lenA;
        }
        while (lenB > lenA) {
            ptrB = ptrB->next;
            --lenB;
        }
        while (ptrA && ptrA != ptrB) {
            ptrA = ptrA->next;
            ptrB = ptrB->next;
        }
        return ptrA;
    }
};

Xác định nút bắt đầu vòng lặp (LeetCode 142)

Phát hiện vòng lặp trong danh sách liên kết thường sử dụng thuật toán Floyd với hai con trỏ di chuyển với tốc độ khác nhau. Khi hai con trỏ gặp nhau, ta đã xác nhận sự tồn tại của vòng. Để tìm chính xác nút bắt đầu của vòng, ta dựa vào đặc tính hình học: khoảng cách từ đầu danh sách đến điểm vào vòng bằng khoảng cách từ điểm gặp nhau đến điểm vào vòng (tính theo chu vi vòng). Việc đặt lại một con trỏ về đầu danh sách và di chuyển cả hai với tốc độ đồng bộ sẽ đảm bảo chúng hội tụ tại nút cần tìm.

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* runner = head;
        ListNode* walker = head;
        bool hasCycle = false;
        while (runner && runner->next) {
            runner = runner->next->next;
            walker = walker->next;
            if (runner == walker) {
                hasCycle = true;
                break;
            }
        }
        if (!hasCycle) {
            return nullptr;
        }
        walker = head;
        while (runner != walker) {
            runner = runner->next;
            walker = walker->next;
        }
        return walker;
    }
};