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

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;
    }
};

删除链表的节点

删除指定值的节点时，关键在于找到待删除节点的前驱节点。如果是头节点被删除，直接返回 head->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->next=cur->next->next;
        return head;
    }
};

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

对于有序链表去重，使用哨兵节点（虚拟头结点）可以简化边界条件的处理，特别是当整个链表都是重复节点的情况。采用前后指针配合，判断连续重复区间，跳过这些区间即可。

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;
            }
            while(rear->next&&rear->val==rear->next->val)
                rear=rear->next;
            if(prev->next!=rear)
                prev->next=rear->next;
            rear=rear->next;
        }
        return newhead->next;
    }
};

链表中倒数第 k 个结点

双指针是解决此类问题的利器。让快指针先走 k 步，然后快慢指针同时移动，当快指针到达末尾时，慢指针正好指向倒数第 k 个节点。注意处理 k 大于链表长度或 k 为 0 的边界情况。

class Solution {
public:
    ListNode* FindKthToTail(ListNode* head, int k) {
        if(!head||k==0) return nullptr;
        ListNode*fast,*slow;
        fast=slow=head;
        while(k>0&&fast){
            fast=fast->next;
            --k;
        }
        while(fast){
            fast=fast->next;
            slow=slow->next;
        }
        return k>0?nullptr:slow;
    }
};

反转链表

反转链表主要有两种经典写法：三指针迭代法和头插法。

三指针法

定义三个指针分别指向当前节点、前一个节点和后一个节点，在遍历过程中逐个翻转指针方向。这种方法逻辑清晰，不易断链。

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;
    }
};

头插法

维护一个新链表的头节点，将原链表节点依次摘下来插入到新链表头部。实现起来非常简洁。

class Solution {
public:
    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;
    }
};

合并两个排序的链表

归并两个有序链表，可以使用哨兵节点辅助构建新链表，或者直接使用递归。

迭代法

设置一个哨兵节点作为新链表的起点，比较两个链表当前节点的值，将较小的节点链接到结果链表尾部，直到其中一个链表为空。

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;
    }
};

递归法

递归逻辑更直观：比较头节点，较小的那个节点的 next 指向剩余部分的合并结果。

class Solution {
public:
    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;
        }
    }
};

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

单链表若有公共节点，则从该节点开始后续路径完全重合。因此可以从尾部往前找，或者通过计算长度差对齐后同步查找。

哈希表法

将第一个链表的所有节点地址存入集合，遍历第二个链表时检查是否存在于集合中。空间复杂度较高，但逻辑简单。

class Solution {
public:
    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;
    }
}; 

长度差法

先计算两个链表的长度和尾部节点是否相同。若尾部不同则无交点；若尾部相同，则让长链表先走差值步，再同步前进，相遇点即为交点。

class Solution {
public:
    ListNode* getlenth(ListNode* cur, int& count) {
        while (cur->next) { ++count; cur = cur->next; }
        return cur;
    }
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1 || !pHead2) return nullptr;
        int count1 = 0, count2 = 0;
        ListNode* end1 = getlenth(pHead1, count1);
        ListNode* end2 = getlenth(pHead2, count2);
        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;
    }
};

复杂链表的复制

复杂链表包含随机指针 random。难点在于如何高效地建立 random 指针的映射关系。

拼接法

将新节点插入到原节点之后，形成 A->A'->B->B' 的结构。这样可以通过原节点的 random 快速定位新节点的 random（即 random->next），最后再将链表拆分为两条。

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(!pHead) return nullptr;
        RandomListNode* cur=pHead;
        while(cur){
            RandomListNode*newnode =new RandomListNode(cur->label);
            newnode->next=cur->next;
            cur->next=newnode;
            cur=cur->next->next;
        }
        cur=pHead;
        while(cur){
            if(cur->random) cur->next->random=cur->random->next;
            cur=cur->next->next;
        }
        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;
    }
};

哈希表法

第一次遍历创建新节点并建立原节点到新节点的映射表，第二次遍历根据映射表设置 random 指针。空间换时间，逻辑更解耦。

#include <unordered_map>
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(!pHead) return nullptr;
        unordered_map<RandomListNode*,RandomListNode*> hash;
        RandomListNode*newhead,*newtail;
        newtail=newhead=nullptr;
        RandomListNode* cur=pHead;
        while(cur){
            RandomListNode*newnode =new RandomListNode(cur->label);
            hash[cur]=newnode;
            if(!newtail) newtail=newhead=newnode;
            else{
                newtail->next=newnode;
                newtail=newtail->next;
            }
            cur=cur->next;
        }
        cur=pHead;
        RandomListNode* copy=newhead;
        while(cur){
            if(cur->random) copy->random=hash[cur->random];
            cur=cur->next;
            copy=copy->next;
        }
        return newhead;
    }
};

链表中环的检测与入口

检测环

使用快慢指针，快指针每次走两步，慢指针每次走一步。如果有环，两者必会在环内相遇；若无环，快指针会先到达空节点。

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;
    }
};

环的入口

基于数学推导，从链表头到入口的距离等于从相遇点到入口的距离。找到相遇点后，让一个指针从头开始，另一个从相遇点开始，同速前进，再次相遇点即为入口。

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(!pHead||!pHead->next) return nullptr;
        ListNode*fast =pHead;
        ListNode*slow =pHead;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow) break;
        }
        if(fast!=slow) return nullptr;
        while(pHead!=fast){
            pHead=pHead->next;
            fast=fast->next;
        }
        return pHead;
    }
};