题目描述

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

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

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

image-20210509195220283
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

补充

ListNode定义如下

public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

解法

    public static ListNode reverseKGroup(ListNode head, int k) {

        if(head == null) return head;
        ListNode a = head;
        ListNode b = head;
        for (int i = 0; i < k; i++) {
            if(b == null) return head;
            b = b.next;
        }
        ListNode newNode = reverse(a, b);
        a.next = reverseKGroup(b, k);
        return newNode;
    }

    // 反转[a,b)个节点
    public static ListNode reverse(ListNode a, ListNode b) {
        ListNode pre,cur,next;
        pre = null;
        cur = a;
        while(cur!=b){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

思路

首先，由一道和他类似的题【LC206. 反转链表】引出我的解法。

在我之前的博客中这道题采用了递归解法。

其实，还有还可以用while循环来解。

    public static ListNode reverse(ListNode a) {
        ListNode pre,cur,next;
        pre = null;
        cur = a;
        while(cur!=null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

上面的代码完成了 给定一个链表头a，将这个链表反转。

具体步骤如下：

这是链表的初始状态：

image-20210509200638636

然后开始执行该函数, 将【前置节点pre】指为null，将【当前节点cur】指向a

 ListNode pre,cur,next;
 pre = null;
 cur = a;
image-20210509201427829

当【当前节点cur】不为空的时候，将【next节点】指向【当前节点cur的下一个】

while(cur!=null){
            next = cur.next;
image-20210509201823579

之后将【当前节点cur】指向【前置节点pre】

cur.next = pre;
image-20210509204603462

然后【pre、cur】开始向后移动一个节点，即：

  • 将【前置节点pre】移动到【当前节点cur】的位置
  • 将【当前节点cur】移动到【后置节点next】的位置

注意：这时候没有移动next是因为不确定移动后【cur】是否为null。

当【cur】为null的时候再移动【后置节点next】会抛出空指针异常。这也是为什么循环的条件是【cur】不为null

pre = cur;
cur = next;
image-20210509204659403

之后在while的循环条件中判断【cur】是否为空， 不为空则进入循环

进入循环中，重复之前的操作。将【next节点】指向【当前节点cur的下一个】

next = cur.next;
image-20210509204747387

之后将【当前节点cur】指向【前置节点pre】

cur.next = pre;
image-20210509204825846

然后【pre、cur】开始向后移动一个节点，即：

  • 将【前置节点pre】移动到【当前节点cur】的位置
  • 将【当前节点cur】移动到【后置节点next】的位置
pre = cur;
cur = next;
image-20210509204902250

以此类推，直到【当前节点cur】为null，停止循环，返回【前置节点pre】

image-20210509205128892

那反转链表的一部分呢，比如反转【a，b）之间的节点 （左闭右开）

image-20210509205449221
image-20210509205551013

你会发现，它其实和我们反转整个链表差不多，反转整个链表的时候，

是相当于反转【a，null）之间的节点，

和反转【a，b）之间的节点有异曲同工之妙啊~

所以说，反转【a，b）之间的节点的代码就应该在他的基础改一改，把

while(cur!=null)

改为

while(cur!=b)

代码如下：

    // 反转[a,b)个节点
    public static ListNode reverse(ListNode a, ListNode b) {
        ListNode pre,cur,next;
        pre = null;
        cur = a;
        while(cur!=b){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

这和 K个一组翻转链表反转 有啥子关系呢？

每K个一组就是相当于区间【a，b）之间的节点有K个，然后一一反转。

这就用到了递归

    public static ListNode reverseKGroup(ListNode head, int k) {

        if(head == null) return head;
        // 区间 [a, b) 包含 k 个待反转元素
        ListNode a = head;
        ListNode b = head;
        for (int i = 0; i < k; i++) {
             // 不足 k 个，不需要反转
            if(b == null) return head;
            b = b.next;
        }
        // 反转前 k 个元素,并获得反转后的头节点
        ListNode newNode = reverse(a, b);
        // 递归反转后续链表并连接起来，这里a反转后由子节点中由头变为尾，所以和a.next拼接
        a.next = reverseKGroup(b, k);
        return newNode;
    }