大气宽屏网站模板企业源码带后台,邦拓网站建设,平台页面设计模板,柳州360优化文章目录 简介链表的常用技巧两数相加原理代码代码|| 两两交换链表中的节点代码原理 重排链表(重要)原理代码 合并 K 个升序链表代码递归代码 K 个一组翻转链表原理代码 简介 大家好,这里是jiantaoyab,这篇文章给大家带来的是链表相关的题目练习和解析,希望大家能相互讨论进步 … 文章目录 简介链表的常用技巧两数相加原理代码代码|| 两两交换链表中的节点代码原理 重排链表(重要)原理代码 合并 K 个升序链表代码递归代码 K 个一组翻转链表原理代码 简介 大家好,这里是jiantaoyab,这篇文章给大家带来的是链表相关的题目练习和解析,希望大家能相互讨论进步 链表的常用技巧 画图 画图能更加清晰,方便我们去理解 引入虚拟的头结点 创建新的头结点指向原来的链表,方便处理边界情况 多定义一个变量 多定义一个next就不用考虑先链接谁的问题 快慢双指针 判断链表中是否有环找环的入口找链表倒数第n个节点 链表逆序用头插 两数相加 https://leetcode.cn/problems/add-two-numbers/ https://leetcode.cn/problems/lMSNwu/ 两数相加|| 原理 代码
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* new_head new ListNode(0); //创建哨兵位头结点ListNode* tail new_head;int x 0;//记录进位ListNode* cur1 l1, *cur2 l2;while(cur1 || cur2 || x){if(cur1){x cur1-val;cur1 cur1-next;}if(cur2){x cur2-val;cur2 cur2-next;}tail-next new ListNode(x % 10);tail tail-next;x / 10;}tail new_head-next;delete new_head;return tail;}
};代码||
class Solution {
public:ListNode* ReserveList(ListNode* head) {ListNode * head nullptr;ListNode * curr head;while(curr) {ListNode* next curr-next;curr-next prev;prev curr;curr next;}return prev;}ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* new_head new ListNode(0); //创建哨兵位头结点ListNode* tail new_head;int x 0;//记录进位l1 ReserveList(l1);l2 ReserveList(l2);ListNode* cur1 l1, *cur2 l2;while(cur1 || cur2 || x){if(cur1){x cur1-val;cur1 cur1-next;}if(cur2){x cur2-val;cur2 cur2-next;}tail-next new ListNode(x % 10);tail tail-next;x / 10;}tail new_head-next;tail ReserveList(tail);delete new_head;return tail;}
};两两交换链表中的节点 https://leetcode.cn/problems/swap-nodes-in-pairs/ 代码
递归的方式 class Solution {
public:ListNode* swapPairs(ListNode* head) {//终止条件是链表只有一个节点 / 链表中没有节点if(head nullptr || head-next nullptr) return head;ListNode* nnext swapPairs(head-next-next);ListNode* newhead head-next;newhead-next head;head-next nnext;return newhead;}
};迭代的方式
原理 class Solution {
public:ListNode* swapPairs(ListNode* head) {// 0个和1个节点直接返回就好if(head nullptr || head-next nullptr) return head;ListNode* newhead new ListNode(0); //哨兵位头结点newhead-next head;ListNode* prev newhead;ListNode* cur prev-next;ListNode* next cur-next;ListNode* nnext next-next;while(cur ! nullptr next ! nullptr){//交换节点prev-next next;next -next cur;cur -next nnext;//更新位置prev cur;cur nnext;if(cur ! nullptr)next cur-next;if(next ! nullptr)nnext next-next;}cur newhead-next;delete newhead;return cur;}
};重排链表(重要) https://leetcode.cn/problems/LGjMqU/ 原理 代码
class Solution {
public:void reorderList(ListNode* head) {// 2节点的直接返回if(head nullptr || head-next nullptr || head-next-next nullptr) return ;//1.找到链表的中间节点ListNode * slow head, *fast head;while(fast fast-next){slow slow-next;fast fast-next-next;}//2.将后半部分链表逆置ListNode* new_head new ListNode(0);ListNode* cur slow-next; slow-next nullptr; //断开链表while(cur){ListNode* next cur-next;cur-next new_head-next;new_head-next cur;cur next;}//3.合并2个链表ListNode* ret_head new ListNode(0);ListNode* prev ret_head;ListNode* cur1 head, *cur2 new_head-next;while(cur1){//先放第一个链表prev-next cur1;cur1 cur1-next;prev prev-next;//再放第二个链表if(cur2){prev-next cur2;cur2 cur2-next;prev prev-next;}}delete new_head;delete ret_head;}
};合并 K 个升序链表 https://leetcode.cn/problems/vvXgSW/ 代码
class Solution {struct cmp {bool operator() (const ListNode* l1, const ListNode* l2) {return l1-val l2-val;}};public:ListNode* mergeKLists(vectorListNode* lists) {//创建小根堆priority_queueListNode* ,vectorListNode*,cmp heap;//让所有链表的头结点加入到小根堆中for(auto l :lists){if(l) heap.push(l);}//合并k个有序链表ListNode* new_head new ListNode(0);ListNode* prev new_head;//小根堆中还有元素说明还有链表没到nullptrwhile(!heap.empty()){ListNode* min heap.top();heap.pop();prev-next min;prev min;if(min-next) heap.push(min-next);}prev-next nullptr;prev new_head-next;delete new_head;return prev;}
};//自己用vs调试的时候,可以加上下面代码调试一步一步看
int main()
{vectorListNode* lists { new ListNode(1, new ListNode(4, new ListNode(5))),new ListNode(1, new ListNode(3, new ListNode(4))),new ListNode(2, new ListNode(6)) };mergeKLists(lists);
}递归代码
class Solution {
public:ListNode* MergeTowList(ListNode* l ,ListNode* r){if(l nullptr) return r;if(r nullptr) return l;ListNode new_head ;new_head.next nullptr;ListNode* cur1 l, *cur2 r, *prev new_head ;while(cur1 cur2){if(cur1-val cur2-val){prev prev-next cur2;cur2 cur2-next;}else{prev prev-next cur1;cur1 cur1-next;}}if(cur1) prev-next cur1;if(cur2) prev-next cur2;return new_head.next;}ListNode* Merge(vectorListNode* lists, int left, int right) {if(left right) return nullptr;if(left right) return lists[left];int mid (left right) 1;ListNode* l Merge(lists, left, mid); ListNode* r Merge(lists, mid 1, right); //合并2个有序链表return MergeTowList(l,r);}
public:ListNode* mergeKLists(vectorListNode* lists) { return Merge(lists, 0, lists.size() - 1);}
};K 个一组翻转链表
原理 代码
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {int N 0;ListNode * p head;while(p){p p-next;N;}N / k; //划分N组ListNode* new_head new ListNode(0);ListNode* prev new_head;ListNode* cur head;for(int i 0; i N; i){ListNode *first cur;for(int j 0; j k; j){ ListNode* next cur-next;cur-next prev-next;prev-next cur;cur next;}prev first;}//把不需要翻转的接上prev-next cur;cur new_head-next;delete new_head;return cur;}
};
