专题：剑指offer

链表

JZ6 从尾到头打印链表

思路：先顺序输出到栈里面 然后再以此从栈顶弹出即可

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
#include <vector>
class Solution {
public:vector<int> printListFromTailToHead(ListNode* head) {stack<int> st;while(head!=nullptr){st.push(head->val);head=head->next;}vector<int> res; while(!st.empty()){res.push_back(st.top());st.pop();}return res;}
};

JZ24 反转链表

思路：借助虚拟头结点进行头插法

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/ListNode* ReverseList(ListNode* head) {// write code here//头插法ListNode* dummy = new ListNode(0);ListNode* cur = head;while(cur!=nullptr){ListNode* next = cur->next;//头插法cur->next=dummy->next;dummy->next=cur;cur = next;}ListNode* res = dummy->next;delete dummy;return res;}
};

JZ25 合并两个排序的链表

方法一：迭代法

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类*/// ListNode* dfs(ListNode* pHead1, ListNode* pHead2){// } ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {// write code here// 迭代写法ListNode* dummp=new ListNode(0);ListNode*pre =dummp;while(pHead1!=nullptr&&pHead2!=nullptr){if(pHead1->val<pHead2->val){ListNode* temp = new ListNode(pHead1->val);pre->next=temp;pre=temp;pHead1=pHead1->next;}else{ListNode* temp = new ListNode(pHead2->val);pre->next=temp;pre=temp;pHead2=pHead2->next;}}while(pHead1!=nullptr){ListNode* temp = new ListNode(pHead1->val);pre->next=temp;pre=temp;pHead1=pHead1->next;}while(pHead2!=nullptr){ListNode* temp = new ListNode(pHead2->val);pre->next=temp;pre=temp;pHead2=pHead2->next;}ListNode* res=dummp->next;delete dummp; return res;}
};

方法二 递归：

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类*/// ListNode* dfs(ListNode* pHead1, ListNode* pHead2){// } ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {// write code hereif(pHead1==nullptr && pHead2==nullptr){return nullptr;}else if(pHead1==nullptr && pHead2!=nullptr){return pHead2;}else if(pHead1!=nullptr && pHead2==nullptr){return pHead1;}// if(pHead1->val<pHead2->val){//ListNode* next1=pHead1->next;// pHead1->next=nullptr;pHead1->next=Merge(next1,pHead2);return pHead1;}ListNode* next2=pHead2->next;// pHead2->next=nullptr;pHead2->next=Merge(pHead1,next2);return pHead2;}
};

JZ52 两个链表的第一个公共结点

方法一：循环遍历两个链表
方法二·：遍历长链表 先快走几步 后面和端链表一起同步走
方法一

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {ListNode* cur1 = pHead1;ListNode* cur2 = pHead2;while(cur1!=cur2){cur1= cur1==nullptr?pHead2:cur1->next;cur2= cur2==nullptr?pHead1:cur2->next;}return cur2;}
};

方法二

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {// 普通解法 就是先走多少步ListNode* cur1 = pHead1;int len1 =0;while(cur1!=nullptr){cur1=cur1->next;len1++;}ListNode* cur2 = pHead2;int len2 =0;while(cur2!=nullptr){cur2=cur2->next;len2++;}int gap =abs(len1-len2);// 保证pHead1指向的是长的链表if(len1<len2){ListNode* temp=pHead1;pHead1=pHead2;pHead2=temp;}cur1 = pHead1;while(gap--){cur1=cur1->next;}cur2 = pHead2;while(cur1!=nullptr){if(cur1==cur2){return cur1;}cur1=cur1->next;cur2=cur2->next;}return cur2;}
};

JZ23 链表中环的入口结点
思路：快慢指针 循环体内 快指针每次走两步 慢指针每次走一步 能够相遇也就是说明有环 然后 慢指针从头开始 另外一个指针从相遇节点开始 判断是否再次相遇 不相遇 这两个指针 每次走一步 走到相遇点就是环入口。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead) {ListNode* slow,*fast;slow=fast=pHead;while(fast!=nullptr&&fast->next!=nullptr){slow=slow->next;fast=fast->next->next;if(slow==fast){// 存在环ListNode* slow = pHead;ListNode* cur = fast;while(slow!=cur){slow=slow->next;cur=cur->next;}return cur;}}return nullptr;}
};

JZ35 复杂链表的复制

参考视频
思路：使用散列表 如下

        unordered_map<RandomListNode*,RandomListNode*> mymap;RandomListNode* cur = pHead;while(cur!=nullptr){mymap[cur]=new RandomListNode(cur->label);cur=cur->next;}

此时节点已经构造出来了 开始准备映射节点的next,以及random关系

完整代码：

/*
struct RandomListNode {int label;struct RandomListNode *next, *random;RandomListNode(int x) :label(x), next(NULL), random(NULL) {}
};
*/
class Solution {// RandomListNode* dfs(RandomListNode* pHead) {//     if (pHead == nullptr) {//         return nullptr;//     }//     RandomListNode* newnode = new RandomListNode(pHead->label);//     cout << "val:" << pHead->label << endl;//     newnode->next = dfs(pHead->next);//     newnode->random = dfs(pHead->random);//     return newnode;// }public:RandomListNode* Clone(RandomListNode* pHead) {// unordered_map<RandomListNode*,RandomListNode*> mymap;RandomListNode* cur = pHead;while(cur!=nullptr){mymap[cur]=new RandomListNode(cur->label);cur=cur->next;}cur = pHead;while(cur!=nullptr){if(cur->next){mymap[cur]->next=mymap[cur->next];}if(cur->random){mymap[cur]->random=mymap[cur->random];}cur=cur->next;}return mymap[pHead];}
};

Z76 删除链表中重复的结点

思路：这里使用率pre以及cur 每次看cur以及cur->next是否相等 不相等 移动pre以及cur 如果相等 移动cur到本次循环不相等的地方

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead) {ListNode* dummy = new ListNode(0);dummy->next = pHead;ListNode*pre = dummy;ListNode*cur = pHead;while(cur!=nullptr){if(cur->next==nullptr || cur->next->val != cur->val){// 准备下一次循环 pre/cur 都需要移动一格pre=cur;cur=cur->next;}else{while(cur->next!=nullptr && cur->val ==cur->next->val){cur=cur->next;}ListNode* nextnode = cur->next;// 直接跳过重复的节点 也就是pre->next直接next到不重复的节点(模拟删除)  注意pre没有移动 移动的是curpre->next = nextnode;cur = nextnode;}}return dummy->next;}
};

JZ18 删除链表的节点

方法一：迭代法
方法二：递归

方法一

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @param val int整型 * @return ListNode类*/ListNode* deleteNode(ListNode* head, int val) {// write code hereif(head==nullptr){return nullptr;}if(head->val!=val){head->next=deleteNode(head->next,val);return head;}return deleteNode(head->next,val);}
};

方法二：

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @param val int整型 * @return ListNode类*/ListNode* deleteNode(ListNode* head, int val) {// write code hereListNode* dummy =new ListNode(0);dummy->next=head;ListNode* pre = dummy;ListNode* cur = head;while(cur!=nullptr){if(cur->val==val){// 你不需要 free 或 delete 被删除的节点 题目已经指出来// ListNode* delenode = cur;cur=cur->next;pre->next = cur;}else{pre=cur;cur=cur->next;}}return dummy->next;}
};