WangBa's Blog

0025. Reverse Nodes in k-Group

LeetCode真的难系列

发布于：2020年10月15日
次浏览

25. Reverse Nodes in k-Group Hard

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.

Follow up:

  • Could you solve the problem in O(1) extra memory space?
  • You may not alter the values in the list’s nodes, only nodes itself may be changed.

Example 1:

img

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

Example 2:

img

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

Example 3:

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

Example 4:

1
2
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

思路：

思路一：迭代

可以结合下面的图和代码进行查看：

image-20201015193552764

代码：

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
public ListNode reverseKGroup(ListNode head, int k) {
    ListNode ans = new ListNode(0);
    ans.next = head;

    ListNode res = ans;
    ListNode end = ans;

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

        end = res;
    }
    return ans.next;
}

private ListNode reverseList(ListNode head) {
    // 递归法
    if (head == null || head.next == null) {
        return head;
    }
    ListNode listNode = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return listNode;
}

时间复杂度：O(n)

空间复杂度：O(1)

思路二：递归

代码：

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
public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null)
        return null;
    ListNode point = head;
    //找到子链表的尾部
    int i = k;
    while(i - 1 >0){
        point = point.next;
        if (point == null) {
            return head;
        }
        i--;
    }
    ListNode temp = point.next;
    //将子链表断开
    point.next = null;

    //倒置子链表，并接受新的头结点
    ListNode new_head = reverseList(head);

    //head 其实是倒置链表的尾部，然后我们将后边的倒置结果接过来就可以了
    //temp 是链表断开后的头指针，可以参考解法一的图示
    head.next = reverseKGroup(temp,k);
    return new_head;
}

private ListNode reverseList(ListNode head) {
    // 递归法
    if (head == null || head.next == null) {
        return head;
    }
    ListNode listNode = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return listNode;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://wangba.me/2020/10/15/0025-Reverse-Nodes-in-k-Group/

更新于：2022年3月26日

Leetcode

LinkedList

评论