链表经典算法实战：相交、回文与随机指针复制

二、链表的回文结构

问题描述

判断一个单链表是否为回文结构，即正着读和反着读都一样。

解题思路

回文链表判断的核心在于对称性验证。我们可以分三步走：

1. 找到中间节点：使用快慢指针法。快指针每次走两步，慢指针每次走一步，当快指针到达末尾时，慢指针正好在中间。
2. 反转后半部分链表：从中间节点开始，将后半部分链表原地反转。
3. 比较前后两部分：从头节点和反转后的中间节点开始，逐个比较节点值是否相同。

完整代码

class PalindromeList {
public:
    // 寻找中间节点
    struct ListNode* middleNode(struct ListNode* head) {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;      // 慢指针每次移动一步
            fast = fast->next->next; // 快指针每次移动两步
        }
        return slow; // 慢指针指向中间节点
    }

    // 反转链表
    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* n1 = NULL, *n2 = head, *n3 = NULL;
        if (n2) n3 = n2->next;
        while (n2) {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3) n3 = n3->next;
        }
        return n1;
    }

    bool chkPalindrome(ListNode* A) {
        struct ListNode* mid = middleNode(A);
        struct ListNode* rmid = reverseList(mid);
        while (rmid && A) {
            if (rmid->val != A->val)
                return false;
            rmid = rmid->next;
            A = A->next;
        }
        return true;
    }
};

三、随机链表的复制

问题描述

实现一个函数，复制一个含有随机指针的链表。随机指针可以指向链表中的任何节点或为空。

解题思路

常规链表复制很简单，但随机指针的存在使得问题复杂化，因为它可能指向尚未复制的节点。我们可以通过'插针法'三步解决：

1. 插入拷贝节点：在原链表的每个节点后插入一个拷贝节点，值与原节点相同。
2. 设置随机指针：拷贝节点的随机指针应指向原节点随机指针所指节点的下一个节点（即其对应的拷贝）。
3. 分离链表：将混合链表分离为原链表和拷贝链表。

struct Node* copyRandomList(struct Node* head) {
    // 1. 拷贝节点插到原节点后边
    struct Node* cur = head;
    while (cur) {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->next = cur->next;
        cur->next = copy;
        copy->val = cur->val;
        cur = copy->next; // cur 走到原链表的下一个
    }

    // 2. 控制 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;
    }

    // 3. 把拷贝链表尾插起来
    struct Node* copyhead = NULL, *copytail = NULL;
    cur = head;
    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;
}

复杂度分析

• 时间复杂度：O(N)，需要三次遍历链表。
• 空间复杂度：O(1)，除了返回的拷贝链表外，仅使用了常数个额外指针。