# leetcode算法之链表

## 1.两数相加

``````/**
* 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) {
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;
}
return prev;
}
};

``````

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

``````/**
* 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* ret = new ListNode(0);
ListNode* prev = ret;
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.重排链表

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

## 4.合并K个升序链表

``````/**
* 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;
}
};
``````
``````/**
* 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个一组翻转链表

``````/**
* 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.计算需要翻转的组数n
int n = 0;
while(cur)
{
n++;
cur = cur->next;
}
n /= k;
//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;
}
};
``````

THE END