数据结构：链表核心算法实战解析

876. 链表的中间节点

寻找中间节点通常使用快慢指针技巧。定义两个指针，一个每次走一步（slow），一个每次走两步（fast）。当快指针到达末尾时，慢指针正好位于中间。对于偶数长度链表，该算法返回的是第二个中间节点，这符合大多数题目的预期。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head; // 慢指针（一次走一步）
    struct ListNode* fast = head; // 快指针（一次走两步）
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

返回倒数第 k 个节点

这是一道经典的面试题。如果只允许遍历一次，就不能先算出总长度。我们可以利用相对距离的概念：让快指针先走 k 步，然后快慢指针同时前进。当快指针到达终点时，慢指针距离终点恰好还有 k 步，即倒数第 k 个位置。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int kthToLast(struct ListNode* head, int k) {
    struct ListNode* fast = head, *slow = head;
    // fast 先运动 k 个节点
    while (k--) {
        fast = fast->next;
    }
    // 两者同步移动，直到 fast 为空
    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow->val;
}

21. 合并两个有序链表

合并有序链表需要逐个比较两个链表的节点值，将较小的节点接入结果链表。为了简化头结点的处理，可以使用哑节点（dummy node）作为临时头，最后返回其下一个节点。这里展示了手动维护头尾指针的写法，逻辑上更直观。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;

    struct ListNode* l1 = list1;
    struct ListNode* l2 = list2;
    struct ListNode* newHead = NULL, *newTail = NULL;

    while (l1 && l2) {
        if (l1->val < l2->val) {
            if (newHead == NULL) {
                newHead = newTail = l1;
            } else {
                newTail->next = l1;
                newTail = newTail->next;
            }
            l1 = l1->next;
        } else {
            if (newHead == NULL) {
                newHead = newTail = l2;
            } else {
                newTail->next = l2;
                newTail = newTail->next;
            }
            l2 = l2->next;
        }
    }
    if (l1) newTail->next = l1;
    if (l2) newTail->next = l2;
    return newHead;
}

160. 相交链表

判断两链表是否相交并找到交点。一种直观的方法是分别计算两条链表的长度，让长链表先走差值步，使两链表剩余长度一致，然后同步遍历。如果存在交点，它们会在某处相遇；否则同时到达 null。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* curA = headA, *curB = headB;
    int lenA = 1, lenB = 1;

    while (curA->next) {
        curA = curA->next;
        ++lenA;
    }
    while (curB->next) {
        curB = curB->next;
        ++lenB;
    }

    // 尾节点不同则不相交
    if (curA != curB) return NULL;

    int gap = abs(lenA - lenB);
    struct ListNode* longList = headA, *shortList = headB;
    if (lenB > lenA) {
        longList = headB;
        shortList = headA;
    }

    while (gap--) {
        longList = longList->next;
    }

    while (longList != shortList) {
        longList = longList->next;
        shortList = shortList->next;
    }
    return longList;
}

138. 随机链表的复制（深拷贝）

带随机指针的链表复制难度较大。除了哈希表法，还有一种空间复杂度 O(1) 的技巧：将复制节点插入到原节点之后，形成 A -> A' -> B -> B' 的结构。这样可以通过原节点的 random 直接定位复制节点的 random，最后再将链表拆分为两条即可。

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
struct Node* copyRandomList(struct Node* head) {
    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;
    }

    // 第二步：设置复制节点的 random 指针
    cur = head;
    while (cur) {
        struct Node* copy = cur->next;
        if (cur->random == NULL) {
            copy->random = NULL;
        } else {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }

    // 第三步：拆分链表
    cur = head;
    struct Node* copyHead = NULL, *copyTail = NULL;
    while (cur) {
        struct Node* copy = cur->next;
        if (copyTail == NULL) {
            copyHead = copyTail = copy;
        } else {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }
        cur = copy->next;
    }
    return copyHead;
}

这些模式在后续图论或树形结构中也会复用，建议结合画图理解指针变化过程，避免死记硬背。