剑指offer第2版：链表系列

一、p58-JZ6 从尾到头打印链表（递归/栈）

从尾到头打印链表_牛客题霸_牛客网

 解法1、递归，每访问一个节点时，先递归输出它后面的节点，再输出该节点自身，但是这样的话可能导致函数的调用层级很深，从而导致函数调用栈溢出。

class Solution {public: void print(vector&ret,ListNode* head){ if(head==nullptr) return; print(ret,head->next); ret.emplace_back(head->val); } vector printListFromTailToHead(ListNode* head) { vector ret; print(ret,head); return ret; }};

解法2：利用栈后进先出的特性，可以避免栈溢出的情况，但是会消耗一部分内存

class Solution {public: vector printListFromTailToHead(ListNode* head) { if(!head) return {}; stack st; vector ret; while(head){//先都入栈 st.push(head->val); head=head->next; } //然后出栈放到数组里面 while(!st.empty()){ ret.emplace_back(st.top()); st.pop(); } return ret; }};

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

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

二、p119-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; }};

三、扩展p122-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; }};

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

链表中倒数最后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 

 五、p142-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; }};

六、p145-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->valval){ 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 val) { pHead1->next = Merge(pHead1->next, pHead2); return pHead1; } else { pHead2->next = Merge(pHead1, pHead2->next); return pHead2; } }};

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

两个链表的第一个公共结点_牛客题霸_牛客网

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

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

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

class Solution { public: ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) { if (!pHead1 || !pHead2) return nullptr; if(pHead1==pHead2) return pHead1;//防止第一个就是 //设计两个辅助栈 stack st1; stack 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 s; while(pHead1){ s.insert(pHead1); pHead1=pHead1->next; } while(pHead2){ if(s.count(pHead2)) return pHead2; pHead2=pHead2->next; } return nullptr; }};

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

复杂链表的复制_牛客题霸_牛客网

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

方法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) { //如果直接拷贝，那么ramdom指针要拷贝的话还需要去原链表里面一次次遍历长度才可以，此时的时间复杂度是n^2 因此我们在创建节点的时候，将新的节点连接在后,然后修改ramdom指针之后，再把链表拆开！！ 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;//迭代 } //此时节点都接上了，然后我们要去修改他们的ramdom指针 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; }};

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

方法2：哈希，第一次遍历创建新链表和原链表每个节点的映射关系，第二遍去改ramdom指针(空间换时间)

#include class Solution {public: RandomListNode* Clone(RandomListNode* pHead) { if(!pHead) return nullptr; //走到这 至少是有一个节点的！ unordered_map 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;//迭代 } //第二次遍历去改新链表的ramdom指针 cur=pHead; RandomListNode* copy=newhead; while(cur){ if(cur->random) copy->random=hash[cur->random];//不为空 就改一下ramdom //然后向后迭代 cur=cur->next; copy=copy->next; } return newhead; }};

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

判断链表中是否有环_牛客题霸_牛客网

 如果链表有环的话，那么用快慢指针，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; }};

十、p139-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); }};