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

题目描述：

给你链表的头节点 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）。
具体实现思绪请看下图：

代码实现

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

1. //判断剩余长度是否>=k，不够则返回nullptr，够则返回k个长度链表的尾结点
2. ListNode *judgeLen_k(ListNode *kHead,int k){
3.         while(k-1){
4.                 if(kHead==nullptr){
5.                         return nullptr;
6.                 }
7.                 kHead=kHead->next;
8.                 --k;
9.         }
10.         return kHead;
11. }
13. //翻转固定个数的链表，返回翻转后的头结点
14. ListNode *reverseList_k(ListNode *kHead,int k){
15.         ListNode *pre=nullptr,*r=kHead,*tmp=kHead;
16.         while(k){
17.                 r=r->next;
18.                 tmp->next=pre;
19.                 pre=tmp;
20.                 tmp=r;
21.                 --k;
22.         }
23.         return pre;
24. }
26. //K 个一组翻转链表
27. ListNode* reverseKGroup(ListNode* head, int k) {
28.         ListNode *dummyHead=new ListNode(0);
29.         //存储答案的尾结点
30.         ListNode *ansTail=dummyHead;
31.         //交换前,k个结点的头
32.         ListNode *kHead=head;
33.         //交换前,k个结点的末尾,不够k个则为nullptr
34.         ListNode *kTail=judgeLen_k(kHead,k);
35.         //保存下一个区间的头
36.         ListNode *next_kHead=nullptr;
37.         while(kTail!=nullptr){
38.                 //保存下一个区间的头
39.                 next_kHead=kTail->next;
40.                 //翻转k个结点
41.                 reverseList_k(kHead,k);
42.                
43.                 //将k个结点翻转后的链表，连接到答案列表
44.                 ansTail->next=kTail;
45.                 kHead->next=next_kHead;
46.                
47.                 //更新答案链表的尾结点
48.                 ansTail=kHead;
49.                 //更新交换前,k个结点的头
50.                 kHead=next_kHead;
51.                 //判断之后的结点是否够k个
52.                 kTail=judgeLen_k(next_kHead,k);
53.                
54.                  
55.         }
56.         ListNode *ansHead=dummyHead->next;
57.         delete dummyHead;
58.         return ansHead;         
59. }

复制代码

代码调试

1. #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个长度链表的尾结点
2. ListNode *judgeLen_k(ListNode *kHead,int k){
3.         while(k-1){
4.                 if(kHead==nullptr){
5.                         return nullptr;
6.                 }
7.                 kHead=kHead->next;
8.                 --k;
9.         }
10.         return kHead;
11. }
13. //翻转固定个数的链表，返回翻转后的头结点
14. ListNode *reverseList_k(ListNode *kHead,int k){
15.         ListNode *pre=nullptr,*r=kHead,*tmp=kHead;
16.         while(k){
17.                 r=r->next;
18.                 tmp->next=pre;
19.                 pre=tmp;
20.                 tmp=r;
21.                 --k;
22.         }
23.         return pre;
24. }
26. //K 个一组翻转链表
27. ListNode* reverseKGroup(ListNode* head, int k) {
28.         ListNode *dummyHead=new ListNode(0);
29.         //存储答案的尾结点
30.         ListNode *ansTail=dummyHead;
31.         //交换前,k个结点的头
32.         ListNode *kHead=head;
33.         //交换前,k个结点的末尾,不够k个则为nullptr
34.         ListNode *kTail=judgeLen_k(kHead,k);
35.         //保存下一个区间的头
36.         ListNode *next_kHead=nullptr;
37.         while(kTail!=nullptr){
38.                 //保存下一个区间的头
39.                 next_kHead=kTail->next;
40.                 //翻转k个结点
41.                 reverseList_k(kHead,k);
42.                
43.                 //将k个结点翻转后的链表，连接到答案列表
44.                 ansTail->next=kTail;
45.                 kHead->next=next_kHead;
46.                
47.                 //更新答案链表的尾结点
48.                 ansTail=kHead;
49.                 //更新交换前,k个结点的头
50.                 kHead=next_kHead;
51.                 //判断之后的结点是否够k个
52.                 kTail=judgeLen_k(next_kHead,k);
53.                
54.                  
55.         }
56.         ListNode *ansHead=dummyHead->next;
57.         delete dummyHead;
58.         return ansHead;         
59. }
60. 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;}

复制代码

反转链表(23_206_简单_C++)(单链表_迭代_递归)：有关反转链表的知识请点击此链接
LeetCode 热题 100_K 个一组翻转链表（31_25)原题链接
接待大家和我沟通交换(✿◠‿◠)

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。