链表高级问题总结

链表高级问题总计及其对应的C语言解决方案，结合算法优化与代码实现

链表高级问题及其对应的C语言解决方案，结合算法优化与代码实现：

---

一、合并K个有序链表
问题描述：将K个已排序的单链表合并为一个升序链表。
解决方案：分治法（时间复杂度O(N log K)）

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    if (listsSize == 0) return NULL;
    if (listsSize == 1) return lists[0];

    int mid = listsSize / 2;
    struct ListNode* left = mergeKLists(lists, mid);
    struct ListNode* right = mergeKLists(lists + mid, listsSize - mid);
    return mergeTwoLists(left, right);
}

思路：递归将链表数组拆分为两半，合并后再合并结果。合并两个链表采用递归法简化指针操作。

---

二、复制带随机指针的链表
问题描述：深拷贝包含随机指针的链表。
解决方案：三次遍历法（时间复杂度O(N)）

struct Node* copyRandomList(struct Node* head) {
    if (!head) return NULL;

    // 1. 插入拷贝节点
    struct Node* cur = head;
    while (cur) {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur = copy->next;
    }

    // 2. 处理random指针
    cur = head;
    while (cur) {
        if (cur->random) {
            cur->next->random = cur->random->next;
        }
        cur = cur->next->next;
    }

    // 3. 分离链表
    struct Node* newHead = head->next;
    cur = head;
    while (cur) {
        struct Node* copy = cur->next;
        cur->next = copy->next;
        if (copy->next) {
            copy->next = copy->next->next;
        }
        cur = cur->next;
    }
    return newHead;
}

关键点：在原节点后插入拷贝节点，通过相对位置设置random指针，最后分离链表。

---

三、奇偶位链表排序
问题描述：奇数位升序，偶数位降序的链表重排为完全升序。
解决方案：分离奇偶链表+反转偶数链表

struct ListNode* sortSpecialList(struct ListNode* head) {
    if (!head || !head->next) return head;

    // 分离奇偶链表
    struct ListNode oddDummy = {0}, evenDummy = {0};
    struct ListNode *oddTail = &oddDummy, *evenTail = &evenDummy;
    int index = 1;
    while (head) {
        if (index % 2 == 1) {
            oddTail->next = head;
            oddTail = oddTail->next;
        } else {
            evenTail->next = head;
            evenTail = evenTail->next;
        }
        head = head->next;
        index++;
    }
    oddTail->next = evenTail->next = NULL;

    // 反转偶数链表
    struct ListNode* prev = NULL, *cur = evenDummy.next;
    while (cur) {
        struct ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    evenDummy.next = prev;

    // 合并两个升序链表
    return mergeTwoLists(oddDummy.next, evenDummy.next);
}

优化：通过奇偶分离和反转实现O(N)时间复杂度。

---

四、检测环形链表
问题描述：判断链表是否有环，并找到环入口。
解决方案：快慢指针法（Floyd算法）

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) {
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return NULL;
}

数学证明：相遇后重置慢指针到头部，同步移动再次相遇点即为入口。

---

五、链表反转（迭代法）
问题描述：反转整个链表或每K个节点。

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, *cur = head;
    while (cur) {
        struct ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

扩展应用：局部反转可通过记录子链表头尾指针实现。

---

六、性能优化策略

1. 内存池管理：预分配节点减少malloc调用次数。
2. 缓存优化：通过顺序访问提升CPU缓存命中率。
3. 无锁并发：使用原子操作实现线程安全链表。

以上方案覆盖链表操作的核心难点，通过合理选择数据结构和算法策略（如分治、哈希映射、指针操作），可高效解决复杂问题。