Reverse K Nodes In Linked List

Tags: ,

Given a singly linked list, reverse every K nodes of the linked list and return the head of the modified linked list.
k is a positive integer.

Good clarifying question: If the number of nodes is not a multiple of k then the last nodes should remain as it is.
Example:

Input:
List = 1->2->3->4->5
K = 2
Output: 
2->1->4->3->5

Input:
List = 1->2->3->4->5
K = 
Output: 
3->2->1->4->5

Reverse K nodes in list: thought process

If I have two chunks of k nodes, one after the other, how would I reverse them in chunks of k nodes? Well, I will first reverse the part which is at the end, return the new head of the reverse part, then I will reverse the first part. Now the most important part, how would I link the first and second parts?
The head of the first part should be the last node of the reversed list, right? The last node of the first part should link to the head of the second part to link these two chunks together.

reverse k nodes in linked list
How can we implement it using recursion? From the above explanation, we know that we have to chunk the linked list into parts with k nodes each till we cannot further divide it. Once we reach the last k nodes part, we apply the method above. Reverse the chunk and return the head of the reversed chunk.
Take care of the last chunk, as it may have less than nodes, in that case, we will return the head of that chunk without reversing the chunk as per the question demands.

It is very important that you know how to reverse a linked list to solve this problem. If you have doubts, I recommend reading that first.

Reverse K nodes : Implementation

    public ListNode reverseKGroup(ListNode head, int k) {
        
        //This is head of current chunk
        ListNode currentHead = head;
        
        //Move k nodes;
        ListNode current = head;
        for(int i=1; i< k && current != null; i++){
            current = current.next;   
        }
        
        if(current != null){
            //Reverse the remaining link list and get the head.
            ListNode reverseHead = reverseKGroup(current.next, k);
            
            //Now reverse the current k nodes list.
            current = head;
            ListNode prev = null;
            ListNode next = head;
        
            int count = 1;
            while(current != null && count <= k){
                next = current.next;
                current.next = prev;
                prev = current;
                current = next;
                count++;
            }
        
            //Link the head with the returned head
            currentHead.next = reverseHead;
            /*Return the new head, which is last 
              node of the current of current k nodes */
            return prev;
        }
        //If there are less than k nodes in last chunk
        else return head;
    }

The time complexity of the implementation is O(n) where n is number of nodes in the list.

Swap 2 nodes in a linked list

In this problem, we have to reverse every pair of nodes in the linked list. For example:

Input:
list = 1->2->3->4->5->6
Output:
2->1->4->3->6->5

This problem is a special case of the above problem of reversing K nodes in a linked list, here k is 2, however, can be implemented in an easier way.

Implementation

    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        
        ListNode temp = head.next;
        ListNode next = head.next.next;
        
        //Reversing the pair
        temp.next = head;
        head = temp;

        //Reverse the remaining list.
        temp.next.next = swapPairs(next);
        
        return head;
    }

The time complexity of the implementation is O(n) where n is number of nodes in the list.