21. Gộp hai danh sách liên kết đã sắp xếp

Cho hai danh sách liên kết tăng dần, hãy gộp chúng thành một danh sách mới cũng theo thứ tự tăng dần.

ListNode* merge(ListNode* a, ListNode* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->val < b->val) {
        a->next = merge(a->next, b);
        return a;
    } else {
        b->next = merge(a, b->next);
        return b;
    }
}

Hoặc dùng cách lặp:

ListNode* merge(ListNode* x, ListNode* y) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (x && y) {
        if (x->val < y->val) {
            tail->next = x;
            x = x->next;
        } else {
            tail->next = y;
            y = y->next;
        }
        tail = tail->next;
    }
    tail->next = x ? x : y;
    return dummy.next;
}

141. Phát hiện vòng lặp trong danh sách

Kiểm tra xem danh sách có chứa vòng lặp hay không.

bool hasCycle(ListNode* head) {
    unordered_set<ListNode*> seen;
    while (head) {
        if (seen.find(head) != seen.end()) return true;
        seen.insert(head);
        head = head->next;
    }
    return false;
}

Dùng con trỏ nhanh-chậm:

bool hasLoop(ListNode* start) {
    if (!start) return false;
    ListNode *slow = start, *fast = start;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

160. Tìm điểm giao nhau của hai danh sách

Xác định nút đầu tiên mà hai danh sách liên kết đơn cùng chia sẻ.

ListNode* findIntersection(ListNode* A, ListNode* B) {
    unordered_set<ListNode*> visited;
    while (A) {
        visited.insert(A);
        A = A->next;
    }
    while (B) {
        if (visited.count(B)) return B;
        B = B->next;
    }
    return nullptr;
}

Giải pháp con trỏ kép:

ListNode* getIntersect(ListNode* p, ListNode* q) {
    ListNode *curP = p, *curQ = q;
    while (curP != curQ) {
        curP = curP ? curP->next : q;
        curQ = curQ ? curQ->next : p;
    }
    return curP;
}

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

Đảo chiều toàn bộ danh sách và trả về đầu danh sách mới.

ListNode* reverse(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

Phiên bản đệ quy:

ListNode* reverseRecursive(ListNode* node) {
    if (!node || !node->next) return node;
    ListNode* newHead = reverseRecursive(node->next);
    node->next->next = node;
    node->next = nullptr;
    return newHead;
}

234. Kiểm tra chuỗi đối xứng

Xác định danh sách có phải là chuỗi đối xứng hay không.

bool isSymmetric(ListNode* head) {
    vector<int> values;
    while (head) {
        values.push_back(head->val);
        head = head->next;
    }
    int i = 0, j = values.size() - 1;
    while (i < j) {
        if (values[i++] != values[j--]) return false;
    }
    return true;
}

Tối ưu không dùng mảng:

ListNode* findMid(ListNode* h) {
    ListNode *s = h, *f = h;
    while (f && f->next) {
        s = s->next;
        f = f->next->next;
    }
    return s;
}

bool checkPalindrome(ListNode* root) {
    ListNode* mid = findMid(root);
    ListNode* revHalf = reverse(mid);
    while (revHalf) {
        if (root->val != revHalf->val) return false;
        root = root->next;
        revHalf = revHalf->next;
    }
    return true;
}

876. Tìm nút giữa danh sách

Trả về nút ở vị trí chính giữa. Nếu có hai nút giữa, trả về nút thứ hai.

ListNode* middle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

2. Cộng hai số biểu diễn bằng danh sách

Mỗi danh sách biểu diễn một số nguyên theo thứ tự ngược, hãy cộng chúng lại.

ListNode* addNumbers(ListNode* num1, ListNode* num2) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    int carry = 0;
    while (num1 || num2 || carry) {
        int total = carry;
        if (num1) { total += num1->val; num1 = num1->next; }
        if (num2) { total += num2->val; num2 = num2->next; }
        curr->next = new ListNode(total % 10);
        curr = curr->next;
        carry = total / 10;
    }
    return dummy.next;
}

19. Xóa nút thứ N từ cuối

Xóa nút thứ N tính từ cuối danh sách và trả về đầu danh sách mới.

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* sentinel = new ListNode(0, head);
    ListNode *fast = head, *slow = sentinel;
    for (int i = 0; i < n; ++i) fast = fast->next;
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }
    slow->next = slow->next->next;
    return sentinel->next;
}

24. Hoán đổi từng cặp nút kề nhau

Hoán đổi các cặp nút liền kề trong danh sách.

ListNode* swapAdjacent(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* first = head;
    ListNode* second = head->next;
    first->next = swapAdjacent(second->next);
    second->next = first;
    return second;
}

138. Sao chép danh sách có con trỏ ngẫu nhiên

Tạo bản sao sâu của danh sách, trong đó mỗi nút có thêm con trỏ random.

unordered_map<Node*, Node*> cloned;

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    if (!cloned.count(head)) {
        Node* newNode = new Node(head->val);
        cloned[head] = newNode;
        newNode->next = copyRandomList(head->next);
        newNode->random = copyRandomList(head->random);
    }
    return cloned[head];
}

142. Tìm điểm bắt đầu vòng lặp

Nếu danh sách có vòng lặp, trả về nút đầu tiên của vòng lặp.

ListNode* detectStartOfCycle(ListNode* head) {
    if (!head) return nullptr;
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            while (head != slow) {
                head = head->next;
                slow = slow->next;
            }
            return slow;
        }
    }
    return nullptr;
}

143. Sắp xếp lại danh sách

Sắp xếp lại danh sách theo dạng: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...

void reorder(ListNode* head) {
    if (!head) return;
    ListNode* mid = findMiddle(head);
    ListNode* secondHalf = mid->next;
    mid->next = nullptr;
    secondHalf = reverse(secondHalf);
    ListNode *first = head, *second = secondHalf;
    while (second) {
        ListNode* temp1 = first->next;
        ListNode* temp2 = second->next;
        first->next = second;
        second->next = temp1;
        first = temp1;
        second = temp2;
    }
}

146. Cache LRU

Thiết kế cấu trúc dữ liệu cache tuân theo chính sách Least Recently Used.

struct Node {
    int key, val;
    Node *prev, *next;
    Node(int k=0, int v=0) : key(k), val(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
    unordered_map<int, Node*> map;
    Node *head, *tail;
    int cap, size;
public:
    LRUCache(int capacity) : cap(capacity), size(0) {
        head = new Node(); tail = new Node();
        head->next = tail; tail->prev = head;
    }
    
    int get(int key) {
        if (!map.count(key)) return -1;
        Node* node = map[key];
        moveToHead(node);
        return node->val;
    }
    
    void put(int key, int value) {
        if (!map.count(key)) {
            Node* newNode = new Node(key, value);
            map[key] = newNode;
            addToHead(newNode);
            if (++size > cap) {
                Node* removed = removeTail();
                map.erase(removed->key);
                delete removed;
                --size;
            }
        } else {
            Node* node = map[key];
            node->val = value;
            moveToHead(node);
        }
    }

private:
    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void addToHead(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
    void moveToHead(Node* node) {
        removeNode(node);
        addToHead(node);
    }
    Node* removeTail() {
        Node* node = tail->prev;
        removeNode(node);
        return node;
    }
};

147. Sắp xếp chèn cho danh sách liên kết

Sử dụng thuật toán sắp xếp chèn để sắp xếp danh sách liên kết.

ListNode* insertionSort(ListNode* head) {
    ListNode dummy(0);
    ListNode *curr = head, *prev = &dummy;
    while (curr) {
        ListNode* next = curr->next;
        ListNode* pos = &dummy;
        while (pos->next && pos->next->val <= curr->val)
            pos = pos->next;
        curr->next = pos->next;
        pos->next = curr;
        curr = next;
    }
    return dummy.next;
}

148. Sắp xếp danh sách liên kết

Sắp xếp danh sách theo thứ tự tăng dần với độ phức tạp O(n log n).

ListNode* mergeSortedLists(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (a && b) {
        if (a->val < b->val) {
            tail->next = a; a = a->next;
        } else {
            tail->next = b; b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

ListNode* sortLinkedList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* mid = slow->next;
    slow->next = nullptr;
    return mergeSortedLists(sortLinkedList(head), sortLinkedList(mid));
}

23. Gộp K danh sách đã sắp xếp

Gộp K danh sách liên kết đã được sắp xếp thành một danh sách duy nhất.

struct Compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
    for (auto& list : lists)
        if (list) pq.push(list);
    
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (!pq.empty()) {
        ListNode* node = pq.top(); pq.pop();
        tail->next = node;
        tail = tail->next;
        if (node->next) pq.push(node->next);
    }
    return dummy.next;
}

25. Đảo ngược từng nhóm K nút

Đảo ngược danh sách theo từng nhóm K nút. Nếu số nút còn lại ít hơn K thì giữ nguyên.

pair<ListNode*, ListNode*> reverseSegment(ListNode* start, ListNode* end) {
    ListNode* prev = end->next;
    ListNode* curr = start;
    while (prev != end) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return {end, start};
}

ListNode* reverseInGroups(ListNode* head, int k) {
    ListNode dummy(0, head);
    ListNode* prevGroupEnd = &dummy;
    while (head) {
        ListNode* groupEnd = prevGroupEnd;
        for (int i = 0; i < k; ++i) {
            groupEnd = groupEnd->next;
            if (!groupEnd) return dummy.next;
        }
        auto [newStart, newEnd] = reverseSegment(prevGroupEnd->next, groupEnd);
        prevGroupEnd->next = newStart;
        prevGroupEnd = newEnd;
        head = newEnd->next;
    }
    return dummy.next;
}