leetcode算法之链表

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(0);ListNode* prev = newhead;int t = 0;ListNode* cur1 = l1,*cur2 = l2;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) {if(head == nullptr || head->next == nullptr) return head;ListNode* ret = new ListNode(0);ListNode* prev = ret;prev->next = head;ListNode* cur = prev->next,*next = cur->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 = ret->next;delete ret;return cur;}
};

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;ListNode* ret = new ListNode(0);ListNode* prev = ret;//1.找中间节点ListNode* slow = head,*fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}//2.将slow后面的链表部分逆序ListNode* newhead = new ListNode(0);ListNode* cur = slow->next;slow->next = nullptr;//将前一段链表和后一段链表断开while(cur){ListNode* next = cur->next;cur->next = newhead->next;newhead->next = cur;cur = next;}//3.合并两个链表ListNode* cur1 = head,*cur2 = newhead->next;while(cur1 || cur2){if(cur1){prev->next = cur1;cur1 = cur1->next;prev = prev->next;}if(cur2){prev->next = cur2;cur2 = cur2->next;prev = prev->next;}}delete ret;delete newhead;}
};

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) {if(lists.size() == 0) return nullptr;if(lists.size() == 1) return lists[0];//使用优先级队列，即最小堆来解决priority_queue<ListNode*,vector<ListNode*>,cmp> heap;ListNode* ret = new ListNode(0);ListNode* prev = ret;for(auto l:lists){if(l) heap.push(l);}while(!heap.empty()){ListNode* t = heap.top();heap.pop();prev->next = t;prev = t;if(t->next) heap.push(t->next);}prev = ret->next;delete ret;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];//1.选择中间元素划分区间int mid = (left+right)>>1;//[left,mid][mid+1,right]//2.处理左右区间ListNode* l1 = merge(lists,left,mid);ListNode* l2 = merge(lists,mid+1,right);//3.合并两个有序链表ListNode* ret = new ListNode(0);ListNode* prev = ret;ListNode* cur1 = l1,*cur2 = l2;while(cur1 && cur2){if(cur1->val <= cur2->val){prev->next = cur1;prev = prev->next;cur1 = cur1->next;}else{prev->next = cur2;prev = prev->next;cur2 = cur2->next;}}if(cur1) prev->next = cur1;if(cur2) prev->next = cur2;prev = ret->next;delete ret;return prev;}
};

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) {//模拟if(head==nullptr || head->next==nullptr) return head;//1.计算需要翻转的组数nint n = 0;ListNode* cur = head;while(cur){n++;cur = cur->next;}n /= k;cur = head;//2.重复n次，长度为n的链表逆序ListNode* ret = new ListNode(0);ListNode* prev = ret;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;}
};