Reverse List Nodes in K-Group (C++, Java, Python)

Linked lists contain a lot of problems, one of them is reversing the nodes of the list in the k groups. This task involves reversing k nodes at a time in a given linked list. In this article, we will discuss an approach to solve this famous leetcode problem and its implementation in C++, Java, and Python.

What is Reverse Nodes in k-Group Problem?

In the Reverse List Nodes in K-Group problem, we are given a head of the linked list, and we are required to reverse the nodes in the k-group. The value of 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, the left-out nodes at the end should remain unchanged.

For example:

Input: List = [1,2,3,4,5,6,7,8]

k=2

Output:

[2,1,4,3,6,5,8,7]

As we can see the nodes are reversed in the groups of 2.

Using 3 Pointers to Reverse Nodes in k-Group

To reverse nodes in k-group, we will use a systematic approach involving the creation of a dummy node and the use of three-pointers (pre, cur, and nex) for reversing each group.

Here are the steps involved in the solutions

First of all, we will Iterate through the linked list to get the length of the list. This step is crucial for determining the number of groups to be processed.
Now we will create a dummy node and point it next to the head of the given linked list. This dummy node will help in simplifying the edge cases.

Now we will create three pointers: “pre”, “curr”, and “nex” to facilitate the reversal of each group.

We will iterate through the linked list until the length of the list to be processed is greater than or equal to the given k. This ensures that there are enough nodes in the remaining list to form a group of k nodes.
Now for each iteration, we will point cur to pre->next and nex to nex->next and start a nested iteration for the length of k. For each inner iteration, modify the links in the following steps:
- cur->next = nex->next
- nex->next = pre->next
- pre->next = nex
- nex = cur->next
After k iteration, we will Move pre to cur and reduce the length by k. This process effectively reverses each group of k nodes.

Let’s see these steps in our example:

Dummy node pointing to the head of the linked list

Now we will initialize pre = dummy head, curr = pre->next, and nex = curr->next

Now we will change links,
- cur->next = nex->next
- nex->next = pre->next
- pre->next = nex
- nex = cur->next

Our first group is reversed now we will start reversing the second group by moving pre to curr and reducing the length by k. And using the same steps.

Now the second group is also reversed, we will move pre to curr and reduce length by k.

Now the third group is also reversed, we will move pre to curr and reduce length by k.

Now the fourth group is also reversed, we will move pre to curr and reduce length by k and here length becomes 0 so no more iteration.

Now we will simply return the dummy’s next which is our modified linked list.

C++ Code

Here is the implementation in C++:

#include<bits/stdc++.h>
using namespace std;

// Node class definition
class node {
public:
    int num;
    node* next;
    node(int a) {
        num = a;
        next = NULL;
    }
};

// Utility function to insert a node in the list
void insertNode(node* &head, int val) {
    node* newNode = new node(val);
    if (head == NULL) {
        head = newNode;
        return;
    }

    node* temp = head;
    while (temp->next != NULL) temp = temp->next;

    temp->next = newNode;
    return;
}

// Utility function to find the length of the list
int lengthOfLinkedList(node* head) {
    int length = 0;
    while (head != NULL) {
        ++length;
        head = head->next;
    }
    return length;
}

// Utility function to reverse k nodes in the list
node* reverseKNodes(node* head, int k) {
    if (head == NULL || head->next == NULL) return head;

    int length = lengthOfLinkedList(head);

    // Create a dummy node to simplify edge cases
    node* dummyHead = new node(0);
    dummyHead->next = head;

    // Pointers for reversing nodes
    node* pre = dummyHead;
    node* cur;
    node* nex;

    // Reverse k nodes at a time
    while (length >= k) {
        cur = pre->next;
        nex = cur->next;
        
        // Perform the reversal within a group of k nodes
        for (int i = 1; i < k; i++) {
            cur->next = nex->next;
            nex->next = pre->next;
            pre->next = nex;
            nex = cur->next;
        }

        // Move pre to the end of the reversed group
        pre = cur;
        length -= k;
    }

    // Return the modified list
    return dummyHead->next;
}

// Utility function to print the list
void printLinkedList(node* head) {
    while (head->next != NULL) {
        cout << head->num << "->";
        head = head->next;
    }
    cout << head->num << "\n";
}

int main() {
    node* head = NULL;

    int k = 2;  // Change the value of k to 2

    // Inserting nodes into the linked list
    insertNode(head, 1);
    insertNode(head, 2);
    insertNode(head, 3);
    insertNode(head, 4);
    insertNode(head, 5);
    insertNode(head, 6);
    insertNode(head, 7);
    insertNode(head, 8);

    // Displaying the original linked list
    cout << "Original Linked List: ";
    printLinkedList(head);

    // Reversing k nodes in the linked list
    cout << "After Reversal of k nodes: ";
    node* newHead = reverseKNodes(head, k);
    printLinkedList(newHead);

    return 0;
}

Python Code

You can do this in Python as well:

class ListNode:
    def __init__(self, x):
        self.num = x
        self.next = None

def insertNode(head, val):
    new_node = ListNode(val)
    if head is None:
        head = new_node
        return head

    temp = head
    while temp.next is not None:
        temp = temp.next

    temp.next = new_node
    return head

def length_of_linked_list(head):
    length = 0
    while head is not None:
        length += 1
        head = head.next
    return length

def reverse_k_nodes(head, k):
    if head is None or head.next is None:
        return head

    length = length_of_linked_list(head)

    dummy_head = ListNode(0)
    dummy_head.next = head

    pre = dummy_head
    cur = None
    nex = None

    while length >= k:
        cur = pre.next
        nex = cur.next

        for i in range(1, k):
            cur.next = nex.next
            nex.next = pre.next
            pre.next = nex
            nex = cur.next

        pre = cur
        length -= k

    return dummy_head.next

def print_linked_list(head):
    while head.next is not None:
        print(head.num, end="->")
        head = head.next
    print(head.num)

if __name__ == "__main__":
    head = None
    k = 2  # Change the value of k to 2

    # Inserting nodes into the linked list
    head = insertNode(head, 1)
    head = insertNode(head, 2)
    head = insertNode(head, 3)
    head = insertNode(head, 4)
    head = insertNode(head, 5)
    head = insertNode(head, 6)
    head = insertNode(head, 7)
    head = insertNode(head, 8)

    # Displaying the original linked list
    print("Original Linked List: ", end="")
    print_linked_list(head)

    # Reversing k nodes in the linked list
    print("After Reversal of k nodes: ", end="")
    new_head = reverse_k_nodes(head, k)
    print_linked_list(new_head)

Java Code

Here is the Java program to reverse nodes in k Group:

import java.util.*;
 public class favtutor {
     static class Node {
    int num;
    Node next;

    Node(int a) {
        num = a;
        next = null;
    }
}
    // Utility function to insert node in the list
    static Node insertNode(Node head, int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = newNode;
            return head;
        }

        Node temp = head;
        while (temp.next != null)
            temp = temp.next;

        temp.next = newNode;
        return head;
    }

    // Utility function to find length of the list
    static int lengthOfLinkedList(Node head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }

    // Utility function to reverse k nodes in the list
    static Node reverseKNodes(Node head, int k) {
        if (head == null || head.next == null)
            return head;

        int length = lengthOfLinkedList(head);

        Node dummyHead = new Node(0);
        dummyHead.next = head;

        Node pre = dummyHead;
        Node cur;
        Node nex;

        while (length >= k) {
            cur = pre.next;
            nex = cur.next;
            for (int i = 1; i < k; i++) {
                cur.next = nex.next;
                nex.next = pre.next;
                pre.next = nex;
                nex = cur.next;
            }
            pre = cur;
            length -= k;
        }
        return dummyHead.next;
    }

    // Utility function to print the list
    static void printLinkedList(Node head) {
        while (head.next != null) {
            System.out.print(head.num + "->");
            head = head.next;
        }
        System.out.println(head.num);
    }

    public static void main(String args[]) {
        Node head = null;
        int k = 3;
        head = insertNode(head, 1);
        head = insertNode(head, 2);
        head = insertNode(head, 3);
        head = insertNode(head, 4);
        head = insertNode(head, 5);
        head = insertNode(head, 6);
        head = insertNode(head, 7);
        head = insertNode(head, 8);

        System.out.print("Original Linked List: ");
        printLinkedList(head);
        System.out.print("After Reversal of k nodes: ");
        Node newHead = reverseKNodes(head, k);
        printLinkedList(newHead);

    }
}

Output:

Original Linked List: 1->2->3->4->5->6->7->8
After Reversal of k nodes: 2->1->4->3->6->5->8->7

The time complexity for this approach is O(N) because the main loop iterates through the linked list, reversing k nodes at a time. In the worst case, each node is visited and reversed exactly once. Since the number of nodes is N, this process also takes O(N) time. The space complexity for this approach is O(1) as no extra space is used.

Conclusion

In conclusion, the leetcode problem of reversing nodes in k-groups within a linked list has been discussed and solved using an optimized approach. The article covered the implementation of the solution in C++, Java, and Python with their complexity analysis. Need more help? get Data Structures assignment help online from top experts.