【算法题攻略】链表

一、习题讲解

1. 两两交换链表中的节点（medium）

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

• 题目描述：

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

示例 1：

• 输入：head = [1,2,3,4]
• 输出：[2,1,4,3]

示例 2：

• 输入：head = [ ]
• 输出：[ ]

示例 3：

• 输入：head = [1]
• 输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

• 代码示例：

classSolution{public:ListNode*swapPairs(ListNode*head){if(head==nullptr||head->next==nullptr)returnhead;ListNode*phead=head;ListNode*cur=phead;ListNode*prev=phead->next;head=prev;// 换位后,头节点的位置也会变,提前设置好新的头节点位置phead=prev->next;while(cur&&prev){if(phead&&phead->next!=nullptr){prev->next=cur;cur->next=phead->next;cur=phead;prev=phead->next;phead=prev->next;}else{prev->next=cur;cur->next=phead;break;}}returnhead;}};

2. 重排链表（medium）

143. 重排链表

• 题目描述：

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

• 输入：head = [1,2,3,4]
• 输出：[1,4,2,3]

示例 2：

• 输入：head = [1,2,3,4,5]
• 输出：[1,5,2,4,3]

• 代码示例：

classSolution{public:voidreorderList(ListNode*head){// 第一步：快慢指针找中间节点ListNode*mid=head;ListNode*prev=head;while(prev->next!=nullptr){prev=prev->next;if(prev->next!=nullptr)prev=prev->next;mid=mid->next;}if(mid==nullptr||mid->next==nullptr)// 链表节点小于3，无需重排return;// 第二步：对中间节点往后的节点进行逆序ListNode*left=mid;ListNode*right=mid->next;while(right){ListNode*tmp=right->next;right->next=left;left=right;right=tmp;}// 第三步：以phead 和 prev两个节点为起点，调整链表ListNode*phead=head;while((phead!=mid)&&(prev!=mid)){ListNode*tmp=phead->next;phead->next=prev;phead=tmp;tmp=prev->next;prev->next=phead;prev=tmp;}mid->next=nullptr;}};

3. 合并 K 个升序链表（hard）

23. 合并 K 个升序链表

• 题目描述：

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

• 输入：lists = [ [1,4,5],[1,3,4],[2,6] ]
• 输出：[1,1,2,3,4,4,5,6]
• 解释：链表数组如下：
  [
  1->4->5,
  1->3->4,
  2->6
  ]
  将它们合并到⼀个有序链表中得到：1->1->2->3->4->4->5->6

示例 2：

• 输入：lists = [ ]
• 输出：[ ]

示例 3：

• 输入：lists = [ [ ] ]
• 输出：[ ]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

• 代码演示：

classSolution{public:structgreater{booloperator()(constListNode*left,constListNode*right){return(left->val)>(right->val);}};ListNode*mergeKLists(vector<ListNode*>&lists){ListNode*head=nullptr;// 小堆，存储节点指针，自定义仿函数（比较节点的val）priority_queue<ListNode*,vector<ListNode*>,greater>pri1;// 将链表数组下，每个链表不为空的头节点加入小堆for(autoit:lists){if(it!=nullptr){pri1.push(it);}}ListNode*cur=nullptr;while(!pri1.empty()){ListNode*tmp=pri1.top();pri1.pop();if(tmp->next!=nullptr)pri1.push(tmp->next);if(head==nullptr){head=tmp;cur=tmp;}>这里是引用else{cur->next=tmp;cur=tmp;}}returnhead;}};

二、练习题

1. K个⼀组翻转链表（hard）

25. K 个一组翻转链表

• 题目描述：

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

• 输入：head = [1,2,3,4,5], k = 2
• 输出：[2,1,4,3,5]

示例 2：

• 输入：head = [1,2,3,4,5], k = 3
• 输出：[3,2,1,4,5]

示例 3：

• 输入：lists = [ [ ] ]
• 输出：[ ]

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000
• 解决链表相关的题目一定要画图！！！

• 代码演示：

classSolution{public:voidreverse(ListNode*left,ListNode*right){ListNode*cur=nullptr;ListNode*prev=nullptr;cur=left->next;if(cur!=right)prev=cur->next;while(left!=right){cur->next=left;left=cur;cur=prev;if(cur&&cur!=right)prev=cur->next;}}ListNode*reverseKGroup(ListNode*head,intk){if(k==1)returnhead;ListNode*phead=head;ListNode*left=nullptr;ListNode*right=nullptr;ListNode*tail=nullptr;head=nullptr;while(phead!=nullptr){left=phead;// 以 k个节点为一组子链表（ left指向子链表头节点，right指向子链表尾节点 ）right=phead;inti=1;for(;i<k;i++){if(right->next!=nullptr)right=right->next;elsebreak;}if(i!=k)break;phead=right->next;// 记录下一次子链表的起点指针if(head==nullptr)head=right;reverse(left,right);// 对子链表进行翻转left->next=phead;if(tail==nullptr)tail=left;// 记录这一次 子链表的尾节点指针else{tail->next=right;tail=left;}}if(head==nullptr)head==phead;returnhead;}};