知识总结
- 常用技术：
1.画图！！——>直观+形象+便于理解
2.引入虚拟”头结点“
- 便于处理边界情况
- 方便对链表操作
3.不要吝啬空间，大胆定义变量
4.快慢双指针——判环、找链表中环的入口、找链表中倒数第n个节点
- 链表中的常用操作
1.创建一个新节点
2.尾插
3.头插
俩数相加
- 题目链接
俩数相加
https://leetcode.cn/problems/add-two-numbers/
- 算法原理
- 代码步骤
/*** 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* cur1 = l1, *cur2 = l2;ListNode* newHead = new ListNode(0);int t = 0;ListNode* tail = newHead;while(cur1 || cur2 || t){if(cur1) {t += cur1->val;cur1 = cur1->next;}if(cur2){t += cur2->val;cur2 = cur2->next;} tail->next = new ListNode(t % 10);t /= 10;tail = tail->next;}tail = newHead->next;delete newHead;return tail;}
};俩俩交换链表中的节点
- 题目链接
俩俩交换链表中的节点https://leetcode.cn/problems/swap-nodes-in-pairs/description/
- 算法原理
- 代码步骤
/*** 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(0);newHead->next = head;ListNode *prev = newHead, *cur = newHead->next;ListNode *next = cur->next, *nnext = cur->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;}
};重排链表
- 题目链接
重排链表https://leetcode.cn/problems/reorder-list/description/
- 算法原理
- 代码步骤
/*** 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* slow = head, *fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}cout << slow->val << " " << slow->next->val << endl;// 逆序——头插ListNode* newHead = new ListNode(0);ListNode *cur = slow->next;slow->next = nullptr;while(cur){slow->next = cur->next;cur->next = newHead->next;newHead->next = cur;cur = slow->next;}// 合并俩个链表ListNode *cur1 = head, *cur2 = newHead->next;ListNode* ret = new ListNode(0);cur = ret;while(cur1){cur->next = cur1;cur = cur->next;if(cur1) cur1 = cur1->next;if(cur2){cur->next = cur2;cur = cur->next;cur2 = cur2->next;}}head = ret->next;delete ret;delete newHead;}
};合并k个升序链表
- 题目链接
合并k个升序链表https://leetcode.cn/problems/merge-k-sorted-lists/
- 算法原理
- 代码展示
/*** 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 {struct cmp{bool operator()(ListNode* l1, ListNode* l2){return l1->val > l2->val;}};
public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, cmp> heap;for(auto ch : lists){if(ch) heap.push(ch);}ListNode* newHead = new ListNode(0);ListNode* prev = newHead;while(!heap.empty()){ListNode* tmp = heap.top();heap.pop();prev->next = tmp;prev = tmp;if(tmp->next) heap.push(tmp->next);}prev = newHead->next;delete newHead;return prev;}
};k个一组翻转链表
- 题目链接
k个一组翻转链表https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
- 算法原理
- 代码展示
/*** 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) {// 计算翻转次数int n = 0;ListNode *tmp = head;while(tmp){tmp = tmp->next;n++;}n = n / k;ListNode newHead;newHead.next = nullptr;ListNode *prev = &newHead, *cur = head;for(int i = 0; i < n; i++){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;return cur;}
};
