Reverse a Linked List in Groups in Kotlin

by

To reverse a linked list in groups, you can follow these steps:

  1. Define a function that takes two arguments – the head node of the linked list and the size of the group.
  2. Traverse the linked list until you reach the end or until you have processed the last group of nodes.
  3. For each group of nodes, reverse the group by swapping the pointers between the nodes in the group. You can do this by maintaining three pointers – prev, curr, and next – and moving them accordingly.
  4. Update the head node of the linked list to point to the last node of the first group.
  5. Repeat steps 3-4 until you reach the end of the linked list.

here’s Kotlin code to reverse a linked list in groups :

Kotlin
class Node(var value: Int) {
    var next: Node? = null
}
fun reverseInGroups(head: Node?, k: Int): Node? {
    var curr = head
    var prev: Node? = null
    var next: Node? = null
    var count = 0    
    // reverse first k nodes of the linked list
    while (curr != null && count < k) {
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
        count++
    }   
    // recursively call the function for remaining nodes
    if (next != null) {
        head?.next = reverseInGroups(next, k)
    }    
    // prev is the new head of the linked list
    return prev
}
fun main() {
    // create a linked list
    val head = Node(1)
    head.next = Node(2)
    head.next?.next = Node(3)
    head.next?.next?.next = Node(4)
    head.next?.next?.next?.next = Node(5)
    head.next?.next?.next?.next?.next = Node(6)
    // reverse in groups of size 2
    val k = 2
    val newHead = reverseInGroups(head, k)
    // print the reversed linked list
    var node: Node? = newHead
    while (node != null) {
        print("${node.value} -> ")
        node = node.next
    }
    print("null")
}
  1. The function takes two arguments: head is the head node of the linked list to be reversed and k is the size of the group in which the list needs to be reversed.
  2. The function defines three variables: curr is the current node being processed, prev is the previous node, and next is the next node in the list. count is used to keep track of the number of nodes processed in the current group.
  3. Inside the while loop, the function reverses the nodes in groups of size k. It does this by swapping the next pointer of the current node with the prev pointer, and then moving prev, curr, and next one node to the right. This continues until count reaches k or until the end of the linked list is reached.
  4. After the while loop, if there are remaining nodes in the list, the function recursively calls itself with the next node as the new head. The result of this recursive call is then assigned to the next pointer of the original head.
  5. Finally, the function returns the prev node, which is the new head of the reversed linked list.

In the main function, we create a linked list with six nodes and call the reverseInGroups function to reverse the nodes in groups of size 2. The newHead variable is assigned the result of this function call.

Then, we traverse the reversed linked list starting from newHead and print each node’s value followed by an arrow. We keep doing this until we reach the end of the linked list, which is indicated by a null value.

The time complexity of the reverseInGroups function is O(n), where n is the number of nodes in the linked list. This is because the function needs to traverse each node in the linked list exactly once. The time complexity of the function is not affected by the group size k.

The space complexity of the function is O(k), where k is the group size. This is because the function uses k variables (curr, prev, next, and count) to keep track of the nodes being processed in the current group. The function uses a constant amount of additional space for each group of nodes being processed, so the total space used is proportional to the group size k.

Leave a Comment