原文链接: https://leetcode-cn.com/problems/reverse-nodes-in-k-group

英文原文

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

 

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Example 3:

Input: head = [1,2,3,4,5], k = 1
Output: [1,2,3,4,5]

Example 4:

Input: head = [1], k = 1
Output: [1]

 

Constraints:

• The number of nodes in the list is in the range sz.
• 1 <= sz <= 5000
• 0 <= Node.val <= 1000
• 1 <= k <= sz

 

Follow-up: Can you solve the problem in O(1) extra memory space?

中文题目

给你一个链表，每 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]

示例 3：

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

示例 4：

输入：head = [1], k = 1
输出：[1]

提示：

• 列表中节点的数量在范围 sz 内
• 1 <= sz <= 5000
• 0 <= Node.val <= 1000
• 1 <= k <= sz

通过代码

高赞题解

一图胜千言，根据图片看代码，马上就懂了

步骤分解:

1. 链表分区为已翻转部分+待翻转部分+未翻转部分
2. 每次翻转前，要确定翻转链表的范围，这个必须通过 k 此循环来确定
3. 需记录翻转链表前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来
4. 初始需要两个变量 pre 和 end，pre 代表待翻转链表的前驱，end 代表待翻转链表的末尾
5. 经过k此循环，end 到达末尾，记录待翻转链表的后继 next = end.next
6. 翻转链表，然后将三部分链表连接起来，然后重置 pre 和 end 指针，然后进入下一次循环
7. 特殊情况，当翻转部分长度不足 k 时，在定位 end 完成后，end==null，已经到达末尾，说明题目已完成，直接返回即可
8. 时间复杂度为 $O(n*K)$ 最好的情况为 $O(n)$ 最差的情况未 $O(n^2)$
9. 空间复杂度为 $O(1)$ 除了几个必须的节点指针外，我们并没有占用其他空间

{:width=600}
{:align=center}

代码如下:

[-Java]
public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode pre = dummy;
    ListNode end = dummy;

    while (end.next != null) {
        for (int i = 0; i < k && end != null; i++) end = end.next;
        if (end == null) break;
        ListNode start = pre.next;
        ListNode next = end.next;
        end.next = null;
        pre.next = reverse(start);
        start.next = next;
        pre = start;

        end = pre;
    }
    return dummy.next;
}

private ListNode reverse(ListNode head) {
    ListNode pre = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}

统计信息

通过次数	提交次数	AC比率
249851	379668	65.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
两两交换链表中的节点	中等