Đảo ngược danh sách liên kết

Một cách hiệu quả để đảo ngược danh sách liên kết là sử dụng kỹ thuật chèn đầu. Ta duyệt qua từng nút trong danh sách gốc, tách từng nút ra và chèn vào đầu danh sách mới. Trong quá trình này, cần lưu trữ con trỏ đến nút kế tiếp trước khi thay đổi liên kết.

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* current = head;
    struct ListNode* newHead = NULL;

    while (current != NULL) {
        struct ListNode* nextNode = current->next;  // Lưu nút kế
        current->next = newHead;                   // Chèn vào đầu danh sách mới
        newHead = current;                         // Cập nhật đầu mới
        current = nextNode;                        // Di chuyển tới nút kế
    }

    return newHead;
}

Hợp nhất hai danh sách liên kết đã sắp xếp

Để hợp nhất hai danh sách đã sắp tăng, ta dùng một nút "canh gác" (sentinel) nhằm đơn giản hóa việc chèn phần tử. Nút này không chứa dữ liệu thực, chỉ giúp tránh xử lý đặc biệt cho trường hợp danh sách rỗng.

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (!list1) return list2;
    if (!list2) return list1;

    struct ListNode sentinel;
    struct ListNode* tail = &sentinel;

    while (list1 && list2) {
        if (list1->val < list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }

    tail->next = list1 ? list1 : list2;

    return sentinel.next;
}

Phân vùng danh sách theo giá trị ngưỡng

Cho một danh sách và giá trị x, phân chia sao cho các phần tử nhỏ hơn x nằm trước. Giải pháp: tạo hai danh sách tạm — một chứa phần tử nhỏ hơn x, một chứa phần tử lớn hơn hoặc bằng. Dùng nút canh gác cho cả hai để đơn giản hóa thao tác chèn đuôi.

ListNode* partition(ListNode* head, int x) {
    ListNode lessHead, greaterHead;
    ListNode *lessTail = &lessHead, *greaterTail = &greaterHead;

    ListNode* curr = head;
    while (curr) {
        if (curr->val < x) {
            lessTail->next = curr;
            lessTail = curr;
        } else {
            greaterTail->next = curr;
            greaterTail = curr;
        }
        curr = curr->next;
    }

    lessTail->next = greaterHead.next;
    greaterTail->next = NULL;

    ListNode* result = lessHead.next;
    return result;
}

Kiểm tra cấu trúc đối xứng trong danh sách

Danh sách có cấu trúc đối xứng nếu đọc từ đầu hay từ cuối đều giống nhau. Chiến lược: tìm điểm giữa danh sách, đảo ngược nửa sau, rồi so sánh với nửa đầu. Nếu tất cả giá trị khớp, danh sách là đối xứng.

// Hàm tìm nút giữa
struct ListNode* findMiddle(struct ListNode* head) {
    struct ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

bool chkPalindrome(struct ListNode* head) {
    if (!head || !head->next) return true;

    struct ListNode* mid = findMiddle(head);
    struct ListNode* reversedSecondHalf = reverseList(mid);

    while (reversedSecondHalf && head) {
        if (reversedSecondHalf->val != head->val)
            return false;
        reversedSecondHalf = reversedSecondHalf->next;
        head = head->next;
    }
    return true;
}

Tìm nút giao nhau của hai danh sách

Để kiểm tra hai danh sách có giao nhau, trước tiên tính độ dài mỗi danh sách. Cho danh sách dài hơn tiến trước một số bước bằng chênh lệch độ dài. Sau đó, cả hai con trỏ cùng di chuyển — nếu chúng gặp nhau tại một nút, đó chính là điểm giao.

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    int lenA = 0, lenB = 0;
    struct ListNode* tempA = headA, *tempB = headB;

    while (tempA->next) { lenA++; tempA = tempA->next; }
    while (tempB->next) { lenB++; tempB = tempB->next; }

    if (tempA != tempB) return NULL;  // Không giao nhau

    int diff = (lenA > lenB) ? lenA - lenB : lenB - lenA;
    struct ListNode* longer = (lenA > lenB) ? headA : headB;
    struct ListNode* shorter = (lenA > lenB) ? headB : headA;

    while (diff--) longer = longer->next;

    while (longer != shorter) {
        longer = longer->next;
        shorter = shorter->next;
    }

    return longer;
}

Phát hiện chu trình trong danh sách liên kết

Dùng hai con trỏ: chậm (slow) di chuyển một bước, nhanh (fast) di chuyển hai bước. Nếu tồn tại chu trình, hai con trỏ chắc chắn sẽ gặp nhau do bài toán đuổi bắt. Nếu fast gặp NULL, danh sách không có chu trình.

bool hasCycle(struct ListNode* head) {
    struct ListNode* slow = head, *fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

Tìm điểm bắt đầu của chu trình

Sau khi phát hiện điểm gặp nhau giữa slow và fast, đặt một con trỏ tại đầu danh sách, một tại điểm gặp. Cả hai di chuyển một bước mỗi lần — điểm chúng gặp lại chính là điểm bắt đầu chu trình. Điều này được chứng minh bằng công thức khoảng cách: L = C - X, với L là khoảng từ đầu đến chu trình, C là chu vi vòng lặp.

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* slow = head, *fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            struct ListNode* start = head;
            while (start != slow) {
                start = start->next;
                slow = slow->next;
            }
            return start;
        }
    }
    return NULL;
}