LeetCode 热题 100_K 个一组翻转链表（31_25_困难

LeetCode 热题 100_K 个一组翻转链表（31_25_困难_C++）(四指针法)

LeetCode 热题 100_K 个一组翻转链表（31_25）

- 题目描述：
- 输入输出样例：
- 题解：
- - 解题思路：
  - - 思路一（四指针法）：
  - 代码实现
  - - 代码实现（思路一（四指针法））：

题目描述：

给你链表的头节点 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]

提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

题解：

解题思路：

思路一（四指针法）：

1、通过题目分析，在每次翻转前需要进行个数的判断，若满足再将k个结点翻转，将翻转后的答案进行连接。
我们发现我们在进行翻转的时候需要保存k个结点的首和尾（kHead和kTail），并且还需要保存kHead之前的一个结点（ansTail）和kTail之后的一个结点(next_kHead)，方便将翻转后的链表进行连接和剩余结点的处理，因此我们需要四个指针（kHead、kTail、ansTail、next_kHead）。

具体实现思路请看下图：
请添加图片描述

代码实现

代码实现（思路一（四指针法））：

//判断剩余长度是否>=k，不够则返回nullptr，够则返回k个长度链表的尾结点 
ListNode *judgeLen_k(ListNode *kHead,int k){while(k-1){if(kHead==nullptr){return nullptr;}kHead=kHead->next;--k;}return kHead; 
} //翻转固定个数的链表，返回翻转后的头结点 
ListNode *reverseList_k(ListNode *kHead,int k){ListNode *pre=nullptr,*r=kHead,*tmp=kHead;while(k){r=r->next;tmp->next=pre;pre=tmp;tmp=r;--k;}return pre;
} //K 个一组翻转链表
ListNode* reverseKGroup(ListNode* head, int k) {ListNode *dummyHead=new ListNode(0); //存储答案的尾结点 ListNode *ansTail=dummyHead;//交换前,k个结点的头ListNode *kHead=head;//交换前,k个结点的末尾,不够k个则为nullptr ListNode *kTail=judgeLen_k(kHead,k);//保存下一个区间的头ListNode *next_kHead=nullptr;while(kTail!=nullptr){//保存下一个区间的头next_kHead=kTail->next;//翻转k个结点reverseList_k(kHead,k);//将k个结点翻转后的链表，连接到答案列表 ansTail->next=kTail;kHead->next=next_kHead;//更新答案链表的尾结点ansTail=kHead;//更新交换前,k个结点的头 kHead=next_kHead; //判断之后的结点是否够k个 kTail=judgeLen_k(next_kHead,k);} ListNode *ansHead=dummyHead->next;delete dummyHead;return ansHead;         
}

代码调试

#include<iostream>
#include<vector>
using namespace std;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){}
}; //尾插法创建单链表
ListNode *createList(vector<int> arr){ListNode *head=nullptr,*tail=nullptr;for(const auto &val:arr){if(head==nullptr){head=tail=new ListNode(val);}else{tail->next=new ListNode(val);tail=tail->next;}}return head;
} //判断剩余长度是否>=k，不够则返回nullptr，够则返回k个长度链表的尾结点 
ListNode *judgeLen_k(ListNode *kHead,int k){while(k-1){if(kHead==nullptr){return nullptr;}kHead=kHead->next;--k;}return kHead; 
} //翻转固定个数的链表，返回翻转后的头结点 
ListNode *reverseList_k(ListNode *kHead,int k){ListNode *pre=nullptr,*r=kHead,*tmp=kHead;while(k){r=r->next;tmp->next=pre;pre=tmp;tmp=r;--k;}return pre;
} //K 个一组翻转链表
ListNode* reverseKGroup(ListNode* head, int k) {ListNode *dummyHead=new ListNode(0); //存储答案的尾结点 ListNode *ansTail=dummyHead;//交换前,k个结点的头ListNode *kHead=head;//交换前,k个结点的末尾,不够k个则为nullptr ListNode *kTail=judgeLen_k(kHead,k);//保存下一个区间的头ListNode *next_kHead=nullptr;while(kTail!=nullptr){//保存下一个区间的头next_kHead=kTail->next;//翻转k个结点reverseList_k(kHead,k);//将k个结点翻转后的链表，连接到答案列表 ansTail->next=kTail;kHead->next=next_kHead;//更新答案链表的尾结点ansTail=kHead;//更新交换前,k个结点的头 kHead=next_kHead; //判断之后的结点是否够k个 kTail=judgeLen_k(next_kHead,k);} ListNode *ansHead=dummyHead->next;delete dummyHead;return ansHead;         
} int main(){vector<int> a={1,2,3,4,5};int k=2;ListNode *head=createList(a);ListNode *test=reverseKGroup(head,k); while(test!=nullptr){cout<<test->val<<"->";test=test->next;}cout<<"null"; return 0;
}