当前位置：首页 > news >正文

专题：剑指offer

news 2025/6/29 12:33:36

链表

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