Reverse in groups of K nodes in a linked list

Given a pointer to the head of a Singly linked list, our objective is to reverse the linked list in groups of K nodes.

Reversing linked list in groups of 3 nodes

Algorithm:

Reversing K nodes can use the reverse linked list algorithm we discussed in an earlier post.

Initialize: 
count = 0
current = head
next = prev = None

1. while current does not become Null and count < k do:
2.       reverse the linked list
3. end while
4. If there are further nodes left in the linked list
5.       recursively call reverse linked list for next node
6.       and store the returned value in head of the current call
7. return prev at each call as new head

The algorithm is fairly simple, keep on reversing the linked list until k nodes are reversed or the linked list end.

As you can see in the above diagram:
After reversing A-B-C to C-B-A
A that was earlier the head of the k nodes group should now point to the next reversed k nodes head which is F.

To do this we have to first reverse the next k nodes and return its new head to link with A.

This can be achieved easily with recursive function calls, which would first reverse the next k nodes and then link it to the previous list's tail.

Code in Python:

# Python program to reverse a linked list in group of given size k


# Node class
class Node:

    # Constructor to initialise data and next
    def __init__(self, data=None):
        self.data = data
        self.next = None


class SinglyLinkedList:

    # Constructor to initialise head
    def __init__(self):
        self.head = None

    # Function to reverse K nodes of linked list
    def reverse_k_nodes(self, head, k):
        current = head
        next = None
        prev = None
        count = 0

        # traverse k nodes ahead reversing the links or until current is not None
        while current is not None and count < k:
            next = current.next
            current.next = prev
            prev = current
            current = next
            count += 1

        # recursive call to the function to reverse the remaining n-k nodes
        if next is not None:
            head.next = self.reverse_k_nodes(next, k)

        # return the new header of the current sublist
        return prev

    # Function to Insert data at the beginning of the linked list
    def insert_at_beg(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    # Function to print the linked list
    def print_data(self):
        current = self.head
        while current is not None:
            print(current.data, '-> ', end='')
            current = current.next
        print('None')

linked_list = SinglyLinkedList()
linked_list.insert_at_beg(8)
linked_list.insert_at_beg(7)
linked_list.insert_at_beg(6)
linked_list.insert_at_beg(5)
linked_list.insert_at_beg(4)
linked_list.insert_at_beg(3)
linked_list.insert_at_beg(2)
linked_list.insert_at_beg(1)
linked_list.print_data()
# call the reverse k nodes function
linked_list.head = linked_list.reverse_k_nodes(linked_list.head, 3)
# print the reversed list
linked_list.print_data()
"""
Outputs:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> None
3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 8 -> 7 -> None
"""

Exercise: Think of how would you perform reverse alternate k nodes in a linked list? 
That is A-B-C-D-E-F-G-H will become C-B-A-D-E-F-H-G
I would give the solution in the next post.

--
Have any questions or suggestions? Post in the comments below!!

By,
Anubhav Shrimal