东营网站开发招聘,手机必备20个软件,沈阳网站制作策划,国外建筑公司网站目录 链表1. 链表的常用技巧和操作总结2. 两数相加3. 两两交换链表中的节点4. 重排链表5. 合并K个升序链表6. K个一组翻转链表 链表
1. 链表的常用技巧和操作总结
常用技巧
画图!!! 更加直观形象, 便于我们理解引入虚拟头节点, 方便我们对链表的操作, 减少我们对边界情况的考… 目录 链表1. 链表的常用技巧和操作总结2. 两数相加3. 两两交换链表中的节点4. 重排链表5. 合并K个升序链表6. K个一组翻转链表 链表
1. 链表的常用技巧和操作总结
常用技巧
画图!!! 更加直观形象, 便于我们理解引入虚拟头节点, 方便我们对链表的操作, 减少我们对边界情况的考虑. 如果没有虚拟头节点我们可能还需要考虑头插时候的情况进行特殊处理 3. 不要吝啬空间, 大胆定义变量 4. 快慢双指针, (判环, 找链表中环的入口, 找链表中倒数第n个节点)
链表中的常用操作
创建一个新的节点 使用new尾插的方法头插的方法 (逆序链表) 2. 两数相加 算法原理:
模拟两数相加的过程即可, 使用头插, 取l1的数, l2的数, 累加到t中. 编写代码:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* newhead new ListNode;ListNode* prev newhead;ListNode* cur1 l1, *cur2 l2;int t 0;while(cur1 || cur2 || t){if(cur1){t cur1-val;cur1 cur1-next;}if(cur2){t cur2-val;cur2 cur2-next;}ListNode* add new ListNode(t % 10);prev prev-next add;t / 10;}prev newhead-next;delete newhead;return prev;}
};3. 两两交换链表中的节点 算法思路: 方法一是使用递归的方法, 方法二就是使用模拟 不要吝啬指针的定义只要我们定义好了上述指针就会发现仅需遍历一遍链表即可讲链表进行交换, 先进行交换, 这里需要修改到三个指针, 如果为偶数的情况下cur和next都不为空, 如果为奇数的情况下next为空, 但是为奇数的情况下我们就不需要进行交换了.
编写代码:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head nullptr || head-next nullptr) return head;ListNode* newhead new ListNode;ListNode* prev newhead, *cur head, *next head-next, *nnext next-next;while(cur next){//交换节点prev-next next;next-next cur;cur-next nnext;//修改指针prev cur;cur nnext;if(cur) next cur-next;if(next) nnext next-next;}cur newhead-next;delete newhead;return cur;}
};4. 重排链表 算法思路: 这里把slow后面的部分逆序有两种策略, 第一种包括slow位置, 第二种slow-next的位置进行逆序, 如果按照第二种可以直接slow-next nullptr讲链表置为空, 如果第一种想要将链表置空需要遍历的时候记录一下位置, 这里我们采用第二种方式只把slow-next的后面置空, 逆序使用双指针法, 合并链表使用头插法, 当然其他方法也可以
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:void reorderList(ListNode* head) {if(head nullptr || head-next nullptr || head-next-next nullptr) return;ListNode* fast head, *slow head;while(fast fast-next){fast fast-next-next;slow slow-next;}ListNode* cur slow-next;slow-next nullptr; ListNode* prev nullptr;while(cur){ListNode* next cur-next;cur-next prev;prev cur;cur next;}ListNode* l1 head;ListNode* l2 prev;ListNode* newhead new ListNode; prev newhead;while(l1){prev prev-next l1;l1 l1-next;if(l2){prev prev-next l2;l2 l2-next;}}delete newhead;}
};/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:void reorderList(ListNode* head) {if(head nullptr || head-next nullptr || head-next-next nullptr) return; //处理边界情况ListNode* fast head, *slow head;while(fast fast-next){fast fast-next-next;slow slow-next;}//头插法进行逆置slow-next后面的部分ListNode* head2 new ListNode;ListNode* cur slow-next;slow-next nullptr;//断开链表while(cur){ListNode* next cur-next;cur-next head2-next;head2-next cur;cur next;}//合并两个链表尾插ListNode* cur1 head, *cur2 head2-next;ListNode* ret new ListNode;ListNode* prev ret;while(cur1){prev-next cur1;prev prev-next; cur1 cur1-next;if(cur2){prev-next cur2;prev prev-next;cur2 cur2-next;}}delete ret;delete head2;return; }
};5. 合并K个升序链表 算法思路: 暴力解法时间复杂度太高了, 而且比较麻烦
模拟, 使用堆这个数据结构, 重载比较函数, 先将所有的头节点插入到堆中, 然后取堆顶元素进行合并, 合并之后如果下一个元素存在把下一个元素插入到堆中, 如果堆为空则合并完毕, 注意这里的const修饰的是指针本身, 而不是修饰这个变量, 因为这个变量不是const类型变量, const位置放置错误会导致报错, 注意类型匹配. /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:class com{public:bool operator()(ListNode* const l1, ListNode* const l2){return l1-val l2-val;}};ListNode* mergeKLists(vectorListNode* lists) {priority_queueListNode*, vectorListNode*,com heap;for(auto x : lists)if(x) heap.push(x);ListNode* newhead new ListNode;ListNode* prev newhead;while(!heap.empty()){ListNode* t heap.top();prev prev-next t;heap.pop();if(t-next) heap.push(t-next);}prev newhead-next;delete newhead;return prev;}
};递归 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeKLists(vectorListNode* lists) {return mergeSort(lists,0,lists.size()-1);}ListNode* mergeSort(vectorListNode* lists,int left,int right){//处理边界if(left right) return nullptr;if(left right) return lists[left];//划分区间int mid (right left) 1;ListNode* l1 mergeSort(lists, left, mid);ListNode* l2 mergeSort(lists,mid1, right);//排列return mergelist(l1,l2);}ListNode* mergelist(ListNode* l1, ListNode* l2){if(l1 nullptr) return l2;if(l2 nullptr) return l1;ListNode* newhead new ListNode;ListNode* prev newhead;while(l1 l2){if(l1-val l2-val){prev prev-next l1;l1 l1-next;}else{prev prev-next l2;l2 l2-next;}}if(l1) prev-next l1;if(l2) prev-next l2;prev newhead-next;delete newhead;return prev;}
};6. K个一组翻转链表 算法思路: 仅需进行模拟即可 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* cur head; int n 0;while(cur){cur cur-next;n;}n / k;ListNode* newhead new ListNode;ListNode* prev newhead;cur head;for(int i 0; i n; i){ListNode* tmp cur;for(int j 0; j k; j){ListNode* next cur-next;cur-next prev-next;prev-next cur;cur next;}prev tmp;}prev-next cur;cur newhead-next;delete newhead;return cur;}
};完
