剑指 Offer 第 2 版：链表核心算法实战

思路三：直接逆序 既然最终返回的是数组，我们可以先按顺序遍历存入数组，最后直接调用 reverse 进行逆序。这是最直观且代码量较少的解法。

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        if (!head) return {};
        vector<int> ret;
        while (head) {
            ret.emplace_back(head->val);
            head = head->next;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

删除链表的节点

题目要求删除值为 val 的节点。关键点在于我们需要找到被删节点的前驱节点，才能修改其 next 指针。

需要注意处理头节点本身就是待删除节点的特殊情况。对于中间或末尾的节点，我们使用一个指针遍历，直到找到前驱节点，然后执行 cur->next = cur->next->next 即可断开连接。

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if (!head) return nullptr;
        if (head->val == val) return head->next;
        
        ListNode* cur = head;
        while (cur->next && cur->next->val != val) {
            cur = cur->next;
        }
        // 此时 cur 指向待删除节点的前驱
        cur->next = cur->next->next;
        return head;
    }
};

删除排序链表中的重复节点

这是一个扩展题，需要删除所有重复出现的节点，只保留不重复的节点。由于链表已排序，相同的节点必然相邻。

这里推荐使用哨兵头结点（Dummy Node），它可以简化对头节点本身可能被删除的情况的处理。定义两个指针 prev 和 rear，prev 始终指向当前确认无误的最后一个节点，rear 用于探测是否有重复。

当发现重复时，rear 继续向后移动直到跳过所有相同值的节点，然后让 prev->next 指向 rear->next，从而切断重复段。

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (pHead == nullptr) return nullptr;
        
        // 哨兵节点，防止讨论整张表都是重复的情况
        ListNode* newhead = new ListNode(0);
        newhead->next = pHead;
        ListNode* prev = newhead;
        ListNode* rear = pHead;
        
        while (rear != nullptr) {
            // 如果没有重复，两个指针一起往后走
            while (rear->next && rear->val != rear->next->val) {
                prev = prev->next;
                rear = rear->next;
            }
            // 如果发现重复了，就让 rear 一直走到不同值的位置
            while (rear->next && rear->val == rear->next->val) {
                rear = rear->next;
            }
            // 如果 prev->next != rear，说明中间有重复节点，需要删除
            if (prev->next != rear) {
                prev->next = rear->next;
            } else {
                prev = prev->next;
            }
            rear = rear->next;
        }
        return newhead->next;
    }
};

链表中倒数第 k 个结点

常规做法是遍历两次：第一次算长度，第二次找位置。但更优解是使用双指针，只需遍历一次。

定义快慢指针，快指针先走 k 步，然后快慢指针同时前进。当快指针到达链表尾部时，慢指针正好位于倒数第 k 个节点。注意要处理 k 大于链表长度的边界情况。

class Solution {
public:
    ListNode* FindKthToTail(ListNode* head, int k) {
        if (!head || k == 0) return nullptr;
        ListNode* fast = head;
        ListNode* slow = head;
        
        // 快指针先走 k 步
        while (k > 0 && fast) {
            fast = fast->next;
            --k;
        }
        // 如果 k 还没走完，说明链表长度不足
        if (k > 0) return nullptr;
        
        // 快慢指针同步移动
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

反转链表

反转链表是面试高频题，主要有两种经典写法。

方法一：三指针迭代 定义三个指针 p1, p2, p3，分别代表当前节点、下一个节点和再下一个节点。在遍历时不断修改 p2->next 指向 p1，实现局部翻转，同时推进指针。注意最后要将原头节点的 next 置为 nullptr。

方法二：头插法 维护一个新链表 newhead，遍历原链表，将每个节点摘下来插入到新链表的头部。这种方法逻辑上更简洁，不需要额外的指针变量来保存后续节点。

class Solution {
public:
    // 方法一：三指针翻转法
    ListNode* ReverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* p1 = head;
        ListNode* p2 = head->next;
        ListNode* p3 = head->next->next;
        
        while (p3) {
            p2->next = p1;
            p1 = p2;
            p2 = p3;
            p3 = p3->next;
        }
        p2->next = p1;
        head->next = nullptr;
        return p2;
    }
    
    // 方法二：头插法
    ListNode* ReverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* newhead = nullptr;
        while (head) {
            ListNode* t = head;
            head = head->next;
            t->next = newhead;
            newhead = t;
        }
        return newhead;
    }
};

合并两个排序的链表

给定两个有序链表，合并成一个有序链表。可以使用哨兵节点（Dummy Node）来简化边界处理，避免单独判断头节点。

思路一：迭代归并 创建一个虚拟头节点，比较两个链表当前节点的值，将较小的节点链接到结果链表后，并移动对应指针。当其中一个链表遍历完后，直接将另一个链表剩余部分接在后面。

思路二：递归 递归的逻辑非常清晰：比较头节点，较小的那个作为新头，其 next 指针指向剩余部分的合并结果。递归终止条件是任一链表为空。

class Solution {
public:
    // 思路一：迭代 + 哨兵节点
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1) return pHead2;
        if (!pHead2) return pHead1;
        
        ListNode* newhead = new ListNode(-1);
        ListNode* rear = newhead;
        
        while (pHead1 && pHead2) {
            if (pHead1->val < pHead2->val) {
                rear->next = pHead1;
                pHead1 = pHead1->next;
            } else {
                rear->next = pHead2;
                pHead2 = pHead2->next;
            }
            rear = rear->next;
        }
        
        if (!pHead1) rear->next = pHead2;
        if (!pHead2) rear->next = pHead1;
        return newhead->next;
    }
    
    // 思路二：递归
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1) return pHead2;
        if (!pHead2) return pHead1;
        
        if (pHead1->val < pHead2->val) {
            pHead1->next = Merge(pHead1->next, pHead2);
            return pHead1;
        } else {
            pHead2->next = Merge(pHead1, pHead2->next);
            return pHead2;
        }
    }
};

两个链表的第一个公共节点

如果两个单链表有公共节点，那么从第一个公共节点开始，之后的所有节点都重合。这意味着它们的尾部一定是相同的。

方法一：辅助栈 利用栈'后进先出'的特性，将两个链表的所有节点分别压入栈中，然后从栈顶开始弹出比较。最后一个相同的节点即为第一个公共节点。时间复杂度 O(M+N)，空间复杂度 O(M+N)。

方法二：长度差法 先遍历两个链表计算长度，让较长的链表先走 |len1 - len2| 步，使两个指针距离尾部一样远。然后同时移动，第一个相遇的节点就是公共节点。此方法只需遍历两次链表。

方法三：哈希集合 将第一个链表的所有节点地址存入 unordered_set，然后遍历第二个链表，检查节点是否存在于集合中。存在即返回。空间换时间，适合快速查找场景。

class Solution {
public:
    // 方法一：借助两个辅助栈
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1 || !pHead2) return nullptr;
        if (pHead1 == pHead2) return pHead1;
        
        stack<ListNode*> st1, st2;
        while (pHead1) { st1.push(pHead1); pHead1 = pHead1->next; }
        while (pHead2) { st2.push(pHead2); pHead2 = pHead2->next; }
        
        if (st1.top() != st2.top()) return nullptr;
        
        ListNode* res = nullptr;
        while (!st1.empty() && !st2.empty()) {
            ListNode* t1 = st1.top();
            ListNode* t2 = st2.top();
            st1.pop();
            st2.pop();
            if (t1 == t2) res = t1;
            else break;
        }
        return res;
    }
    
    // 方法二：长度差法
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1 || !pHead2) return nullptr;
        
        int count1 = 0, count2 = 0;
        ListNode* end1 = pHead1, *end2 = pHead2;
        
        while (end1->next) { ++count1; end1 = end1->next; }
        while (end2->next) { ++count2; end2 = end2->next; }
        
        if (end1 != end2) return nullptr;
        
        if (count1 > count2) {
            while (count1 - count2) { --count1; pHead1 = pHead1->next; }
        } else {
            while (count2 - count1) { --count2; pHead2 = pHead2->next; }
        }
        
        while (pHead1 != pHead2) {
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        return pHead1;
    }
    
    // 方法三：哈希集合
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1 || !pHead2) return nullptr;
        if (pHead1 == pHead2) return pHead1;
        
        unordered_set<ListNode*> s;
        while (pHead1) { s.insert(pHead1); pHead1 = pHead1->next; }
        while (pHead2) {
            if (s.count(pHead2)) return pHead2;
            pHead2 = pHead2->next;
        }
        return nullptr;
    }
};

复杂链表的复制

复杂链表除了 next 指针外，还有一个 random 指针指向任意节点或空。难点在于 random 指针的拷贝，如果直接遍历查找，时间复杂度会达到 O(N^2)。

方法一：拼接法（模拟） 在原链表每个节点后插入一个新节点，形成 A -> A' -> B -> B' 的结构。这样可以通过原节点的 next 快速定位 random 对应的副本节点。修改完 random 后，再将链表拆分为两个。

方法二：哈希映射 第一次遍历创建新节点并存入哈希表，建立原节点到新节点的映射关系。第二次遍历根据哈希表设置 random 指针。虽然空间复杂度增加，但逻辑更清晰，避免了复杂的指针操作。

class Solution {
public:
    // 方法一：拼接法
    RandomListNode* Clone(RandomListNode* pHead) {
        if (!pHead) return nullptr;
        
        // 1. 复制节点并拼接
        RandomListNode* cur = pHead;
        while (cur) {
            RandomListNode* newnode = new RandomListNode(cur->label);
            newnode->next = cur->next;
            cur->next = newnode;
            cur = newnode->next;
        }
        
        // 2. 设置 random 指针
        cur = pHead;
        while (cur) {
            if (cur->random) cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        
        // 3. 拆分链表
        RandomListNode* newhead = new RandomListNode(-1);
        RandomListNode* newtail = newhead;
        cur = pHead;
        while (cur) {
            RandomListNode* temp = cur->next;
            cur->next = cur->next->next;
            newtail->next = temp;
            newtail = newtail->next;
            cur = cur->next;
        }
        return newhead->next;
    }
    
    // 方法二：哈希映射
    RandomListNode* Clone(RandomListNode* pHead) {
        if (!pHead) return nullptr;
        
        unordered_map<RandomListNode*, RandomListNode*> hash;
        RandomListNode* newhead = nullptr, *newtail = nullptr;
        RandomListNode* cur = pHead;
        
        // 1. 创建新节点并建立映射
        while (cur) {
            RandomListNode* newnode = new RandomListNode(cur->label);
            hash[cur] = newnode;
            if (!newhead) newhead = newtail = newnode;
            else { newtail->next = newnode; newtail = newnode; }
            cur = cur->next;
        }
        
        // 2. 设置 random 指针
        cur = pHead;
        RandomListNode* copy = newhead;
        while (cur) {
            if (cur->random) copy->random = hash[cur->random];
            cur = cur->next;
            copy = copy->next;
        }
        return newhead;
    }
};

判断链表中是否有环

使用快慢指针（Floyd 判圈算法）。定义 fast 每次走两步，slow 每次走一步。如果链表有环，fast 最终会在环内追上 slow；如果无环，fast 会先到达 nullptr。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return false;
        
        ListNode* fast = head;
        ListNode* slow = head;
        
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) return true;
        }
        return false;
    }
};

链表中环的入口节点

找到环的入口点可以利用数学性质：设链表头到入口距离为 a，入口到相遇点距离为 b，相遇点到入口距离为 c。

当快慢指针在环内相遇时，fast 走过的路程是 slow 的两倍。推导可得 a = c。因此，当一个指针回到链表头，另一个指针保持在相遇点，两者同步每次走一步，再次相遇的点即为环的入口。

另一种思路是将环断开，转化为求两个链表的第一个公共节点问题。

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if (!pHead || !pHead->next) return nullptr;
        
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        
        // 1. 找相遇点
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        
        if (fast != slow) return nullptr; // 无环
        
        // 2. 找入口点
        while (pHead != fast) {
            pHead = pHead->next;
            fast = fast->next;
        }
        return pHead;
    }
};