ToB企服应用市场:ToB评测及商务社交产业平台

标题: LeetCode 热题 100_K 个一组翻转链表（31_25_困难_C++）(四指针法) [打印本页]
作者: 嚴華    时间: 7 天前
标题: 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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4