【基础算法】链表

1.两数相加

两数相加
在这里插入图片描述

/*** 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(-1);ListNode* cur1 = l1, *cur2 = l2;ListNode* prev = newhead;int t = 0;while(cur1 || cur2 || t){if(cur1) {t += cur1->val;cur1 = cur1->next;}if(cur2) {t += cur2->val;cur2 = cur2->next;}prev->next = new ListNode(t % 10);prev = prev->next;t /= 10;}prev = newhead->next;delete newhead;return prev;}
};

2.两两交换链表中的节点

两两交换链表中的节点
在这里插入图片描述

/*** 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) {ListNode* newhead = new ListNode(-1);newhead->next = head;ListNode* prev = newhead;ListNode* cur = newhead->next;ListNode* next = cur == nullptr ? nullptr : cur->next;ListNode* nnext = next == nullptr ? nullptr : next->next;while(cur && next){prev->next = next;next->next = cur;cur->next = nnext;prev = cur;cur = prev->next;next = cur == nullptr ? nullptr : cur->next;nnext = next == nullptr ? nullptr : next->next;}prev = newhead->next;delete newhead;return prev;}
};

3.重排链表

重排链表
在这里插入图片描述

/*** 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;// 1.找到链表的中间结点 -- 快慢双指针ListNode* slow = head, *fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}// 2.将链表的slow->next后面的链表逆序组成一个新的链表ListNode* head2 = new ListNode(-1);ListNode* cur = slow->next;slow->next = nullptr;while(cur){ListNode* next = cur->next;cur->next = head2->next;head2->next = cur;cur = next;}// 3.将两个链表合并ListNode* ret = new ListNode(-1);ListNode* cur1 = head, *cur2 = head2->next;ListNode* prev = ret;//记录一下尾节点while(cur1){//先放第一个链表prev->next = cur1;cur1 = cur1->next;prev = prev->next;if(cur2){prev->next = cur2;prev = prev->next;cur2 = cur2->next;}}delete head2;delete ret;}
};

4.合并 K 个升序链表

合并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 {struct cmp{bool operator()(const ListNode* l1, const ListNode* l2){return l1->val > l2->val;}};
public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, cmp> heap;ListNode* head = new ListNode(-1);//让所有的lists的头结点进入堆for(auto list : lists)if(list) heap.push(list);//合并链表ListNode* prev = head;while(!heap.empty()){ListNode* t = heap.top();heap.pop();prev->next = t;prev = t;if(t->next) heap.push(t->next);}prev = head->next;delete head;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(vector<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);}ListNode* merge(vector<ListNode*>& lists, int left, int right){if(left > right) return nullptr;if(left == right) return lists[left];int mid = (left + right) >> 1;ListNode* l1 = merge(lists, left, mid);ListNode* l2 = merge(lists, mid + 1, right);return mergeTowList(l1, l2);}ListNode* mergeTowList(ListNode* l1, ListNode* l2){if(l1 == nullptr) return l2;if(l2 == nullptr) return l1;ListNode head;ListNode* prev = &head;head.next = nullptr;ListNode* cur1 = l1, *cur2 = l2;while(cur1 && cur2){if(cur1->val <= cur2->val){prev = prev->next = cur1;cur1 = cur1->next;}else{prev = prev->next = cur2;cur2 = cur2->next;}}if(cur1) prev->next = cur1;if(cur2) prev->next = cur2;return head.next;}
};

5.K 个一组翻转链表

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) {// 1.先求出需要翻转几组int n = 0;ListNode* cur = head;while(cur){cur = cur->next;n++;}n /= k;ListNode* ret = new ListNode(-1);ListNode* prev = ret;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;prev = ret->next;delete ret;return prev;}
};