【刷题篇】链表

文章目录

• 1、两数相加
• 2、两两交换链表中的节点
• 3、 重排链表
• 4、 合并 K 个升序链表
• 5、 K 个一组翻转链表

1、两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* cur1=l1;ListNode* cur2=l2;ListNode* head=new ListNode(0);ListNode* cur=head;int dummy=0;while(cur1||cur2){int a=0;int b=0;if(cur1){a=cur1->val;dummy+=a;cur1=cur1->next;}if(cur2){b=cur2->val;dummy+=b;cur2=cur2->next;}ListNode* newNode=new ListNode(dummy%10);cur->next=newNode;cur=cur->next;dummy/=10;}if(dummy!=0){ListNode* newNode=new ListNode(dummy%10);cur->next=newNode;}cur=head->next;delete head;//释放内存return cur;}
};

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

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

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 = 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 = newHead->next;delete newHead;return cur;}
};

3、 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

class Solution {
public:void reorderList(ListNode* head) {ListNode* fast=head;ListNode* slow=head;ListNode* new1=slow;//找中间节点while(fast&&fast->next){fast=fast->next->next;slow=slow->next;} //将后半部分链表进行逆序ListNode* midnode=slow->next;slow->next=nullptr;ListNode* head2=new ListNode(0);while(midnode){ListNode* next=midnode->next;midnode->next=head2->next;head2->next=midnode;midnode=next;}ListNode* new2=head2->next;//合并ListNode* dummy=new ListNode(0);ListNode* cur=dummy;while(new1){dummy->next=new1;dummy=dummy->next;new1=new1->next;if(new2){dummy->next=new2;dummy=dummy->next;new2=new2->next;}}head=cur->next;}
};

4、 合并 K 个升序链表

给定一个链表数组，每个链表都已经按升序排列。
请将所有链表合并到一个升序链表中，返回合并后的链表。

class Solution {
public:struct cmp{bool operator()(const ListNode* l1,const ListNode* l2){return l1->val>l2->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*,vector<ListNode*>,cmp> heap;//让所有都节点进入小根堆for(auto l : lists){if(l) heap.push(l);}//合并ListNode* ret=new ListNode(0);ListNode* prev=ret;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;}
};

5、 K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* cur=head;int n=0;while(cur){n++;cur=cur->next;}n=n/k;ListNode* newhead=new ListNode(0);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;}
};