leetcode25.K个一组翻转链表/翻转链表_给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。 k 是一个正整数,

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

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5
1
2
3
4
5

说明 :

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

完整代码

这道题说难也难，说简单也不为过，只要保证在链表翻转的过程中链表不会断开。总能找到正确的结果，好了。不废话了，直接看基本思想

基本思想：
核心思想:递归
这道题可以分解成两步递归：

• 翻转每K个子部分时，利用递归实现
• 翻转整个链表时，利用递归实现（下述代码在翻转整个链表时，未采用递归）

好了，基本思想是这样，下面来看每一部分的递归如何实现 ：

1. 翻转K个子节点： 在翻转的过程中，一定要记住其前驱结点
   先将该节点的后继节点进行递归翻转；
   再处理该节点，该节点的后继是其前驱结点（链表1->2->3，翻转后2的后继是1）；
   递归的终止条件是：递归完这k个节点时，停止
2. 翻转整个链表： 在翻转的整个过程中，一定要将每组节点之间连接好
   第一个组节点，不用处理其前驱；第二组节点以及后面的每组节点的前驱是上一组节点翻转前的起始节点，所以要记住该节点，翻转完其后面一组节点后，连接上。
   整个链表翻转完后，头节点是初始链表的第k个节点，这里一定要考虑整个链表不足k个节点的时候。
   在调用翻转K个子节点传参时需要注意：初始调用时，其前驱结点是该组节点翻转前的最后一个节点的下一个节点（1->2->3->4->5,k=2,翻转3->4后，应当传递的前驱结点是5,目的是在翻转后和后面未翻转的节点连接上）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* sp,*ep,*p=head,*new_h,*pre=new ListNode(0),*ppre=new ListNode(0);
        if(head==NULL||k<=0)
            return NULL;
        while(p!=NULL){
            sp=p;//该组的起始节点
            int i=0;
            while(i<k-1&&p->next!=NULL){
                p=p->next;
                ++i;
            }
            ep=p;//该组的终止节点
            p=p->next;//记录下一组的起始节点
            pre=ppre;//上一组k个节点的开始节点
            ppre=sp;//该次k个节点的开始节点
            
            if(i==k-1){//翻转K个节点
                if(sp==head)
                    new_h=ep;
                //初始调用时，其前驱结点是该组节点翻转前的最后一个节点的下一个节点（1->2->3->4->5,k=2,翻转3->4后，应当传递的前驱结点是5,目的是在翻转后和后面未翻转的节点连接上）
                invert(sp,ep->next,k);
                //逆转完后需要和上一次逆转结果连接上
                if(sp!=head){//第一组不需要和之前的组连接
                    pre->next=ep;//上一组的最后一个节点和该组翻转之前的最后一个节点进行连接
                }
            }
            else{//不足k个，保持原序
                if(sp==head)
                    new_h=head;    
                break;
            }
            
        }
        return new_h;
    }
private:
    void invert(ListNode* head,ListNode* pre,int k){
        if(k==1){
            head->next=pre;
            return;
        }        
        invert(head->next,head,k-1);
        head->next=pre;        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

执行结果：通过
显示详情
执行用时 :24 ms, 在所有 cpp 提交中击败了79.05%的用户
内存消耗 :9.9 MB, 在所有 cpp 提交中击败了74.23%的用户
1
2
3
4

能否将翻转整个链表的过程转化为递归的形式呢？
当然可以，看如下代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        //递归翻转
        if(head==NULL||k<0)
            return NULL;
        
        //查验该节点后面是否有k个节点
        ListNode *sp,*ep,*p;
        int i=0;
        p=head;
        sp=p;
        while(i<k-1&&p->next!=NULL){
            p=p->next;
            ++i;
        }
        ep=p;
        
        //不足k个节点，递归终止条件
        ListNode* post;
        if(i!=k-1){
            return sp;//不进行翻转，直接返回起始节点
        }
        
        //递归
        //整体翻转
        ep->next=reverseKGroup(ep->next,k); 
        //局部翻转
        invert(sp,ep->next,k);
        return ep;
    }
private:
    void invert(ListNode* head,ListNode* pre,int k){
        if(k==0){
            return;
        }        
        invert(head->next,head,k-1);
        head->next=pre;        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

不得不承认递归时间效率低，但是写起来代码，比非递归形式容易，因为递归的过程省去了很多链表连接的步骤

执行结果：通过
显示详情
执行用时 :28 ms, 在所有 cpp 提交中击败了46.04%的用户
内存消耗 :9.7 MB, 在所有 cpp 提交中击败了86.00%的用户
1
2
3
4

非递归
采用非递归的思想来翻转链表，这道题虽然是自己做的，但是调试了好半天才AC，而且自己的思路还比较麻烦，后来看到公众号上一篇文章发现链表还是面试中会涉及到的手撕代码的知识点，于是乎，参考了评论区最热的思想，写出了如下代码。

参考：评论区

基本思想：

• 从头开始遍历链表，记录起始位置，找到第k个节点，记录结尾位置，将结尾的next域置为NULL，并记录下一组的起始位置
• 将这K个节点进行翻转，返回翻转后的头节点，并将头节点连接在已经逆转好的链表的尾部

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        //采用非递归的思想来翻转链表
        if(head==NULL||k<=0)
            return NULL;
        ListNode *dummy=new ListNode(0),*p=head,*pre;
        dummy->next=head;//dummy便于处理头节点
        pre=dummy;//pre指向上一组的最后一个节点
        while(p){
            //找到从p开始的k个节点
            int i=0;
            ListNode* sNode=p,*eNode;
            while(p->next!=NULL && i<k-1){
                p=p->next;
                ++i;
            }//循环完后p指向该组的第k个节点
            eNode=p;
            p=p->next;//p指向下一组的第一个节点
            eNode->next=NULL;//设置这个节点的目的是为了知道这一组节点的结束的节点
            
            //判断是否能构成一组节点
            if(i==k-1){
                pre->next=reverse(sNode);
                pre=sNode;
            }
            else{
                pre->next=sNode;
                break;
            }
        }
        return dummy->next;
    }
private:
    ListNode* reverse(ListNode* head){
        ListNode* p=head,*pre=NULL,*next;
        while(p){
            next=p->next;
            p->next=pre;
            pre=p;
            p=next;
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

执行结果：通过
显示详情
执行用时 :24 ms, 在所有 cpp 提交中击败了78.75%的用户
内存消耗 :9.6 MB, 在所有 cpp 提交中击败了96.16%的用户
1
2
3
4

二刷

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head == NULL || k < 2)
            return head;
        ListNode *p = head, *st = p, *next;
        int cnt = 0;
        while(p && cnt < k - 1){
            cnt++;
            p = p->next;            
        }
        if(p){
            next = p->next;
            ListNode *temp = reverseKGroup(next, k);
            p->next = NULL;
            ListNode *nhead = NULL;
            reverseKNode(st, nhead);
            
            st->next = temp;
            head = nhead;
        }
        return head;
    }
private:
    void reverseKNode(ListNode * head, ListNode * &pre){
        if(head == NULL)
            return;
        ListNode * next = head->next;
        head->next = pre;
        pre = head;
        head = next;
        reverseKNode(head, pre);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42