做平面vi网站,网站建设自助搭配系统,wordpress去除顶部,小程序logo一键生成器目录 一#xff0c; 链表常用技巧和操作总结二#xff0c;算法原理和代码实现2.两数相加24.两两交换链表中的节点143.重排链表23.合并k个升序链表25.k个一组翻转链表 三#xff0c;算法总结 一#xff0c; 链表常用技巧和操作总结 有关链表的算法题也是一类常见并且经典的题… 目录 一 链表常用技巧和操作总结二算法原理和代码实现2.两数相加24.两两交换链表中的节点143.重排链表23.合并k个升序链表25.k个一组翻转链表 三算法总结 一 链表常用技巧和操作总结 有关链表的算法题也是一类常见并且经典的题型这些题要使用数据结构中我们手搓的链表结构也要使用STL中的 list 容器。 下面是几点常用操作的总结 (1) 善于画图。 (2) 引入虚拟头结点。 方便处理边界情况就是当没节点第一次头插或尾插的时候的那个判断引入虚拟头结点就可以避免这个判断(写成 ptail newHead)。 (3) 不要吝啬空间大胆定义变量。 (4) 快慢双指针的使用。 主要应用是判环找链表中环的入口找链表中倒数第 n 个节点。 (5) 解决链表类的题一般是创建一个新节点尾插操作头插操作。 我们在学习数据结构时也做过许多有关链表类的经典题目请浏览【C/数据结构与算法】10道链表经典OJ。 里面的一些题目与本篇文章的题目也是有关联的这篇文章算是进阶篇。 二算法原理和代码实现
2.两数相加 算法原理 这道题是一道简单的模拟题模拟两数相加即可。 定义两个指针 cur1和cur2用于遍历两个链表再定义一个整数 t 用于进位。用 t 和每个节点的值相加取出 t 的个位创建新节点。 细节问题 (1) 这里要注意的细节就是链表是逆序的其实这也是方便我们操作因为我们可以直接从个位开始相加。 (2) 1. 循环条件cur1 || cur2 || t 这里要或t是原因当两个指针都走完时t里可能还有进位还需要尾插 (3) 要销毁哨兵位头节点 代码实现
class Solution
{
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* cur1 l1, *cur2 l2;ListNode* newHead new ListNode(), *ptail newHead; // 虚拟头节点int t 0; // 记录进位while(cur1 || cur2 || t){if(cur1) {t cur1-val;cur1 cur1-next;}if(cur2) {t cur2-val;cur2 cur2-next;}ListNode* newNode new ListNode(t % 10);ptail-next newNode;ptail newNode;ptail-next nullptr;t / 10;}ListNode* pcur newHead-next;delete newHead;return pcur;}
};24.两两交换链表中的节点 算法原理 本题也是一道模拟题重点是画图看图写代码!!! 定义四个指针 根据交换后的链表进行指针的修改(绿色字)一直循环迭代。 结束条件 (1) 偶数个节点时 cur 已经指向空了next 和 nnext 也无效了此时结束循环。 (2) 奇数个节点时 next 已经指向空了 nnext 无效了此时也结束循环。 代码实现
class Solution
{
public:ListNode* swapPairs(ListNode* head) {if(head nullptr) return nullptr;ListNode* newHead new ListNode(), *prev newHead;ListNode* cur head, *next cur-next;ListNode* nnext nullptr;if(next) nnext next-next;prev-next cur;while(cur next){// 交换节点prev-next next;next-next cur;cur-next nnext;// 修改指针prev cur;cur prev-next;if(cur) next cur-next;if(next) nnext next-next;}ListNode* pcur newHead-next;delete newHead;return pcur;}
};143.重排链表 算法原理 这道题比较有综合性通过分析可以发现 重排后的链表 合并两个链表(原链表的前半段 原链表的后半段逆置)。 所以这道题的思路是 (1) 找到链表的中间节点 (2) 把后半部分逆序 (3) 合并两个链表 代码实现
class Solution
{
public:// 找中间节点ListNode* FindMiddleNode(ListNode* head){ListNode* slow head, *fast head, *prev head;while(fast fast-next){prev slow;slow slow-next;fast fast-next-next;}prev-next nullptr; // 与后半段断开return slow;}// 逆置后半部分链表ListNode* reverseList(ListNode* head){ListNode* phead head, *ptail nullptr;while(phead){ListNode* next phead-next;// 头插法phead-next ptail;ptail phead;phead next;}return ptail;}void reorderList(ListNode* head) {// 处理特殊情况if(head-next nullptr || head-next-next nullptr) return;ListNode* mNode FindMiddleNode(head);ListNode* rNode reverseList(mNode);// 合并两个链表ListNode* newHead new ListNode(), *ptail newHead;ListNode* n1 head, *n2 rNode;while(n1 n2){ptail-next n1;ptail ptail-next;n1 n1-next;ptail-next n2;ptail ptail-next;n2 n2-next;}if(n1) ptail-next n1;if(n2) ptail-next n2;delete newHead;}
};23.合并k个升序链表 算法原理 解法1暴力解法利用合并两个有序链表的思想。先把第一个和第二个链表进行合并得到一个新链表再用新链表和第三个链表进行合并…。 假设有 k 个链表每条链表的平均节点有 n 个则时间复杂度为n(k-1) n(k-2) n(k-3) … n -- O(n * k^2)。大概率超时。 解法2利用优先级队列进行优化。 假设有 k 个链表建一个大小为 k 的小根堆把所有链表的第一个节点都扔进小根堆中堆顶节点就是最小值取出堆顶节点和虚拟头结点进行链接再移到下一个节点… 合并链接找出最小值的节点总的时间复杂度为O(n * k * logk)。 易错/细节问题 (1) 优先级队列的第三个模板参数不能直接写成 greaterListNode * 因为这样比较的是地址要写一个仿函数!! (2) 把链表的所有头节点都入队列时要注意传递的链表为空的处理。 代码实现
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 pq;// 把所有头结点进小根堆for (auto l : lists)if (l) pq.push(l);// 合并k个有序链表ListNode* newhead new ListNode(), * ptail newhead;while (!pq.empty()){ListNode* pcur pq.top();pq.pop();ptail-next pcur;ptail pcur;if (pcur-next) pq.push(pcur-next);}ListNode* ret newhead-next;delete newhead;return ret;}
}; 解法3分治-递归 和归并分治的思想一样 假设有 k 个链表那么就有 logk 层递归回退时每个链表的每个节点都执行 logk 次合并每个链表的平均节点有 n 个所以时间复杂度为O(n * k * logk)。 易错/细节问题 (1) 有两个递归出口区间不存在和区间里只有一个链表。 (2) 合并两个有序链表时链表为空的情况。 代码实现
class Solution
{
public:ListNode* mergeKLists(vectorListNode* lists) {return merge(lists, 0, lists.size()-1);}ListNode* merge(vectorListNode* lists, int left, int right){if(left right) return nullptr;if(left right) return lists[left];// 找中点int mid left (right - left) / 2;// [left, mid] [mid1, right]// 合并左右两边ListNode* l1 merge(lists, left, mid);ListNode* l2 merge(lists, mid1, right);// 合并两个有序链表return mergeTwoList(l1, l2);}ListNode* mergeTwoList(ListNode* l1, ListNode* l2){// 处理特殊情况if(l1 nullptr) return l2;if(l2 nullptr) return l1;ListNode head; // 把虚拟节点开在栈上head.next nullptr;ListNode* ptail head;while(l1 l2){if(l1-val l2-val){ptail-next l1;ptail ptail-next;l1 l1-next;}else{ptail-next l2;ptail ptail-next;l2 l2-next;}}if(l1) ptail-next l1;if(l2) ptail-next l2;return head.next;}
};25.k个一组翻转链表 算法原理 这也是一道模拟题算法流程比较简单 (1) 先求出需要逆序多少组n。 (2) 重复 n 次长度为 k 的链表的逆序即可 。 (3) 把不需要逆序的接上。 细节问题 (1) 这里需要记录第n次头插的开始位置每次进行新一轮逆序时都要记住该位置。 (2) 如果使用while循环则每逆序完一组后 k 要重新赋值不然就一直都是k0了。 代码实现
class Solution
{
public:ListNode* reverseKGroup(ListNode* head, int k){// 先求出要逆序多少组int n 0;ListNode* phead head;while (phead){phead phead-next;n;}n / k;// 重复 n 次长度为 k 的链表逆序phead head;ListNode* newhead new ListNode(), * prev newhead;for (int i 0; i n; i){ListNode* tmp phead; // 记录每一组的起点for (int j 0; j k; j){ListNode* next phead-next;phead-next prev-next;prev-next phead;phead next;}prev tmp;}// 把不需要翻转的接上prev-next phead;ListNode* ret newhead-next;delete newhead;return ret;}
};三算法总结 通过上面的若干道题目可以发现大多数链表类的题目本质上是模拟题最重要的就是画图分清各个指针指向哪里。
