Reverse Node in K-Group

About the Problem:

In this problem, we are provided with a linked list and an integer, k. Here we need to reverse every k node in the linked list so that if the last group has less than k node we leave it as such.

Example 1:
Input: [2,6,9,4,1,3]
K = 3
Output: [9,6,2,3,1,4]

Explanation: The length of the given linked list is divisible by k, therefore there won’t be any left nodes. So, reverse the first three nodes and go ahead and do the same for the other groups.

Example 2:
Input: [8,5,1,9,3,7,2]
K = 2
Output: [5,8,9,1,7,3,2]

Explanation: The length of the given linked list is not divisible by k, therefore there will be left nodes. Reverse the first three nodes and go ahead and do the same with the rest, so we are now left with one node.

Approach #1: Recursive

Algorithm:

1. Make a recursive call with the head node and integer k.

2. Declare three pointers to the node current initialized to head (current traversing node) and next, previous initialize to NULL.

3. Now reverse the first k nodes of the linked list. We maintain the previous and next pointer while traversing through the k nodes.

4. The previous pointer points to the last traversed node eventually, after reversing it points to the first node of the reversed list group. The next pointer points to the next node after traversing the linked list group.

5. After reversing the current group list we recursively call, which returns the head of the next reversed group and we assign it to the next head pointer.

6. At last, we return the previous pointer as it contains the head of the k-reversed linked list.

Code:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>

using namespace std;

class Node {
  public: int data;
  Node * next;
};

Node * kReverse(Node * head, int k) {

  Node * current = head;
  Node * next = NULL, * prev = NULL;
  int count = 0;

  while (current != NULL && count < k) {
    next = current - > next;
    current - > next = prev;
    prev = current;
    current = next;
    count++;
  }

  if (next != NULL)
    head - > next = reverse(next, k);

  return prev;
}

void insert(Node ** head, int data) {

  Node * new_node = new Node();
  new_node - > data = data;
  new_node - > next = ( * head);
  * head = new_node;
}

void printList(Node * node) {
  while (node != NULL) {

    cout << node - > data << " ";
    node = node - > next;
  }
}

int main() {

  int n, x, k;
  cin >> n >> k;
  Node * head = NULL;

  for (int i = 0; i < n; i++) {
    cin >> x;
    insert( & head, x);
  }

  cout << "Given linked list \n";
  printList(head);
  head = reverse(head, k);
  cout << "\nK-reversed Linked list \n";
  printList(head);
}

Input:
7 3
8 5 1 9 3 7 2

Output:
Given linked list
2 7 3 9 1 5 8
K-reversed Linked list
3 7 2 5 1 9 8

Time complexity: O(n), we are looping the linked list only once.
Space complexity O(n), we are making n/k recurring calls generally giving a complexity of O(n).

Approach #2: Iterative

To counter the recursion we just use one more loop; it runs length/k times and follows the same approach as above.

Code:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>

using namespace std;

class Node {
  public: int data;
  Node * next;
};

Node * reverse(Node * head, int k) {

  Node * current = head;
  Node * next = NULL, * prev = NULL;
  int count = 0;

  while (current != NULL && count < k) {
    next = current - > next;
    current - > next = prev;
    prev = current;
    current = next;
    count++;
  }

  if (next != NULL)
    head - > next = reverse(next, k);

  return prev;
}

void insert(Node ** head, int data) {

  Node * new_node = new Node();
  new_node - > data = data;
  new_node - > next = ( * head);
  * head = new_node;
}

void printList(Node * node) {
  while (node != NULL) {

    cout << node - > data << " ";
    node = node - > next;
  }
}

Node * kReverse(Node * head, int k) {
  if (!head)
    return head;
  if (k == 0 || k == 1)
    return head;

  Node * dummy = new Node();
  dummy - > data = 0;
  dummy - > next = head;
  Node * pre = dummy;
  int len = 0;
  Node *
    let = head;
  while (let) {
    len++;
    let =
    let - > next;
  }

  for (int i = 0; i < len / k; i++) {
    for (int j = 0; j < k - 1; j++) {

      Node * temp = pre - > next;
      pre - > next = head - > next;
      head - > next = head - > next - > next;
      pre - > next - > next = temp;
    }
    pre = head;
    head = head - > next;
  }

  return dummy - > next;
}

int main() {

  int n, x, k;
  cin >> n >> k;
  Node * head = NULL;

  for (int i = 0; i < n; i++) {
    cin >> x;
    insert( & head, x);
  }

  cout << "Given linked list \n";
  printList(head);
  head = kReverse(head, k);
  cout << "\nK-reversed Linked list \n";
  printList(head);
}

Input:
7 3
8 5 1 9 3 7 2

Output:
Given linked list
2 7 3 9 1 5 8
K-reversed Linked list
3 7 2 5 1 9 8

Time complexity: O(n), we are traversing the linked list only once.
Space complexity O(1), we only declare some variables and pointers.