剑指 Offer 第 2 版：链表算法详解

解法 3：因为该题返回数组，所以直接保存在数组里然后直接逆序即可！

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

二、JZ18 删除链表的节点

因为我们需要找到前面的节点链接后面的节点，所以我们必须停留在该节点的前一个节点。

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

三、扩展 JZ18 删除排序链表的重复节点（前后指针）

我们要用两个指针，左开右闭。这里要考虑特别多的特殊情况，如：全部相同，全部不相同，部分相同等。为了方便解题我们定义哨兵头结点，主要是应对全部相同的情况。

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead==nullptr) return nullptr;
        //prev 和 rear 前开后闭
        //定义一个虚拟头节点
        ListNode*newhead=new ListNode(0);//哨兵节点 是为了防止讨论整张表都是重复的情况
        newhead->next=pHead;
        ListNode* prev=newhead; //prev 始终在前面
        ListNode* rear=pHead;
        while(rear!=nullptr){//一直处理到尾巴
            //如果没有重复 就两个一起往后走
            while(rear->next&&rear->val!=rear->next->val){//为了保证前开后闭 所以要比 next
                prev=prev->next;
                rear=rear->next;
            }
            //如果发现重复了 就让 rear 走
            while(rear->next&&rear->val==rear->next->val) rear=rear->next;
            //此时有 3 种情况 前两种可以一起搞
            //1、(prev.rear] 正常在中间
            //2、(prev.rear] 但此时 rear->next==nullptr 此时后面要全部去掉
            //3、没有重复 这种情况 prev->next==rear 就可以不用处理了 不管
            if(prev->next!=rear) prev->next=rear->next;//此时是前两种情况 就直接开始删
            rear=rear->next; //无论是第一种还是第二种 都要让 rear 指向下一个
        }
        return newhead->next;
    }
};

四、JZ22 链表中倒数第 k 个结点（前后指针）

可以遍历两次链表，第一次链表算长度，然后根据长度算出倒数第 k 个是第几个，然后第二次再去找，但是还有更好的方法只需要遍历一次链表即可。

可以定义两个指针，一个指针先走 k 步，再让另一个指针跟在后面，使用'前后指针'的方式，当前面的指针到达结尾，后面的指针，也就是倒数第 k 个节点（但是要注意 k 超过节点数的情况）。

class Solution {
public:
    //倒数第 k 个节点 用快慢指针 当快指针先走完的时候 此时慢指针就是倒数 k
    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;
        }
        //此时有两种情况 要么 k>0 说明不存在 k==0 说明可以找到
        return k>0?nullptr:slow;
    }
};

注意 k 是无符号整数，如果是 0 的话，一定不能让他 -1。

五、JZ24 反转链表（三指针/头插）

1、定义三个指针，整体右移，边移动，边翻转，保证不会断链。

class Solution {
public:
    //1、三指针翻转法 2、头插法
    ListNode* ReverseList(ListNode* head) {
        if(!head||!head->next) return head;//此时就没必要翻转了
        //能走到这至少是有两个节点的
        ListNode*p1=head;
        ListNode*p2=head->next;
        ListNode*p3=head->next->next;
        while(p3){//p3 为空的时候就不进去了
            p2->next=p1;
            p1=p2;
            p2=p3;
            p3=p3->next;
        }
        p2->next=p1;
        head->next=nullptr;//头指针要让他为空！！！
        return p2;
    }
};

2、可以采用头插思想进行翻转

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

六、JZ25 合并两个排序的链表（双指针/递归）

思路 1：可以一个一个节点的归并，可以搞一个哨兵节点。

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

思路 2：可以递归完成

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

七、JZ52 两个链表的第一个公共节点 (双指针/栈/set)

题目要求是单链表，每个节点只有一个 next 指针，因此从第一个公共节点开始，之后他们所有的节点都是重合的，不可能再出现分叉！

我们会发现如果两个链表有公共节点，那么至少链表的尾部一定是公共节点，那么如果能够从尾部开始走那么最后一个相同的节点就是第一个公共节点，但是因为单链表不可能从尾部开始走，所以这里我们就必须借助栈结构'后进先出'的特性！！

方法 1：借助两个辅助栈，然后将节点全部丢到栈里面，然后从栈顶开始遍历直到找到最后一个相同的节点。

class Solution {
public:
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1 || !pHead2) return nullptr;
        if(pHead1==pHead2) return pHead1;//防止第一个就是
        //设计两个辅助栈
        stack<ListNode*> st1;
        stack<ListNode*> st2;
        while(pHead1){
            st1.push(pHead1);
            pHead1=pHead1->next;
        }
        while (pHead2) {
            st2.push(pHead2);
            pHead2=pHead2->next;
        }
        if(st1.top()!=st2.top()) return nullptr;
        while(!st1.empty()&&!st2.empty()){
            ListNode* t1=st1.top(),*t2=st2.top();
            st1.pop();
            st2.pop();
            if(st1.empty()||st2.empty()||st1.top()!=st2.top()) return t1;
            //判空是为了防止其中一个链表的头结点是另一个链表的子节点的情况
        }
        return nullptr;
    }
};

方法 2：本质是让长的链表先走 abs（length1-length2）步，后面大家的步调一致，往后找第一个地址相同的节点，就是题目要求的节点，所以需要各自遍历两次链表。

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

方法 3：直接把其中一个链表节点都保存到 set 里面，然后遍历另一个链表，只要出现了就返回

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

八、JZ35 复杂链表的复制 (模拟/哈希)

该题的难点就在于如果直接拷贝，那么 random 指针要拷贝的话还需要去原链表里面一次次遍历长度才可以，此时的时间复杂度是 n^2。因此我们在创建节点的时候，将新的节点连接在原链表后面，然后修改 random 指针之后，再把链表拆开！！

方法 1：模拟，让新表接在原表的后面，然后修改 random 指针之后，再把表拆下来返回

/* struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) : label(x), next(NULL), random(NULL) { }
}; */
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        //如果直接拷贝，那么 random 指针要拷贝的话还需要去原链表里面一次次遍历长度才可以，此时的时间复杂度是 n^2 因此我们在创建节点的时候，将新的节点连接在后，然后修改 random 指针之后，再把链表拆开！！
        if(!pHead) return nullptr;
        //走到这 至少是有一个节点的！
        RandomListNode* cur=pHead;//帮助我们进行遍历
        while(cur){
            RandomListNode*newnode =new RandomListNode(cur->label);//创建新节点
            //将新节点接到 cur 后面
            newnode->next=cur->next;
            cur->next=newnode;
            cur=cur->next->next;//迭代
        }
        //此时节点都接上了，然后我们要去修改他们的 random 指针
        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 向后接
            cur->next=cur->next->next;
            //该节点接在新表后面
            newtail->next=temp;
            newtail=newtail->next;
            cur=cur->next;//向后迭代
        }
        return newhead->next;
    }
};

上述问题主要是为了搜索 random 指针指向节点而产生的效率问题，所以我们把他接在原链表的节点后面是为了方便通过原链表快速修改 random 指针，那么如果我们可以直接让新节点和原节点建立联系呢？？比如说通过哈希表建立映射关系！！

方法 2：哈希，第一次遍历创建新链表和原链表每个节点的映射关系，第二遍去改 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;//迭代
        }
        //第二次遍历去改新链表的 random 指针
        cur=pHead;
        RandomListNode* copy=newhead;
        while(cur){
            if(cur->random) copy->random=hash[cur->random];//不为空 就改一下 random
            //然后向后迭代
            cur=cur->next;
            copy=copy->next;
        }
        return newhead;
    }
};

九、扩展 JZ23 链表判环（快慢指针）

如果链表有环的话，那么用快慢指针，fast 会逐步接近追上 slow，如果无环那么 fast 最后会走向空

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

十、JZ23 链表中环的入口节点（快慢指针 + 环性质）

解法 1：利用相遇点到入口点的距离=链表头到入口点的距离 这个性质

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

解法 2：在相遇点将链表拆开，转化成两个链表的找第一个相交节点的问题

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;
    }
    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;//不相等说明没有环
        //要把环给断掉
        fast=fast->next;
        slow->next=nullptr;
        return FindFirstCommonNode(pHead,fast);
    }
};