K个一组翻转链表

发表于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

LeetCode题目，25. Reverse Node in k-Group

先看题目描述

sPpgEj.png

大意就是给定一个链表和一个整数 k，让我们以 k 个节点为一组进行翻转，尾部多余的节点就保持原样，让我们返回翻转后的链表

算法和思路

这题不涉及很复杂的算法，都是一些与链表有关的基础操作，但是实现过程中要考虑的细节很多

大致思路就是先计算出链表的长度 len，然后将 len 整除 k ，求出一共要对多少组节点进行翻转，将每组节点划分到一个子链表里

接下来就是对一个个子链表进行翻转，对子链表进行翻转的操作不难，但要注意将子链表进行翻转后，要将该子链表的头部与上一个子链表的尾部相连，该子链表的尾部与下一个子链表的头部相连，还有最后返回的结果应该是翻转后链表的头节点

具体实现看下面代码吧

算法源码

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
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) {
            return head;
        }
        int len = 0;
        ListNode next;
        ListNode curHead;
        ListNode cur = head;
        ListNode pre = head;
        ListNode preTail = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        int cnt = len / k;
        cur = head;
        for (int i = 0; i < cnt; i++) {
            curHead = cur;
            for (int j = 0; j < k; j++) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            if (i == 0) {
                head = pre;
            } else {
                preTail.next = pre;
            }
            preTail = curHead;
        }
        preTail.next = cur;
        return head;
    }
}