25. Reverse Nodes in k-Group

2020, Dec 05 2 mins read

1. Description

Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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.

2. Example

Example 1

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

Example 2

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

3. Constraints

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

4. Solutions

Linked List

n is the number of nodes in head
Time complexity: O(n)
Space complexity: 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
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        ListNode dummy(0, head);
        ListNode *tail = &dummy;
        while (head != nullptr) {
            int count = 0;
            for (auto iter = head; count < k && iter != nullptr; ++count) {
                iter = iter->next;
            }

            if (count < k) {
                break;
            }

            ListNode *prev = nullptr, *curr = head, *next = nullptr, *last = head;
            for (int i = 0; i < k; ++i) {
                next = curr->next;
                curr->next = prev;
                prev = curr;
                curr = next;
            }

            tail->next = prev;
            last->next = curr;

            tail = last;
            head = curr;
        }

        return dummy.next;
    }
};

Search

Tags