K个一组反转链表

链表难的地方就在于细节比较多，这道题目的意思就是：

给定一个链表
给定一个k
每k个结点作为一组，然后把这一组进行反转，最后返回反转过的链表

题解

首先，因为可能会修改头节点，所以我们最好加一个dummy结点来作为头节点返回。我们来分解一下整个任务，首先是反转链表，可以使用递归或者迭代

1
2
3
4
5
6
7
8
9


public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode node = reverseList(head.next);
    head.next,next = head;
    head.next = null;
    return node;
}

上述的递归代码可以帮助我们完成反转链表的操作。现在我们来看看怎么完成k个一组的反转吧。

首先是获取当前的k个字符串，假设这里有如下的几个结点：

1

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

假设给定的k是3，我们来进行模拟一下

首先要反转前3个元素，那么就得断开3与4之间的连接，并且头节点可能会被修改，那么我们最好要加一个dummy结点来进行辅助。

1

dummy -> 1 -> 2 -> 3 断开 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

代码

 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


class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode start = dummy;
        while (true) {
            ListNode end = start;
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            if (end == null) break;
            // 记录下一组的开头
            ListNode headOfNextGroup = end.next;
            // 断开
            end.next = null;
            // 第一组开头
            ListNode headOfCurGroup = start.next;
            // 新的头节点
            ListNode endOfCurGroup = reverseList(headOfCurGroup);
            start.next = endOfCurGroup;
            // 连接起来
            headOfCurGroup.next = headOfNextGroup;
            // 移动start指针，移动至最后一个结点
            start = headOfCurGroup;
        }
        return dummy.next;
    }

    private ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}