Reverse Nodes in k-Group

This page explains Java solution to problem Reverse Nodes in k-Group using Linked List data structure.

Problem Statement

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

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 then left-out nodes in the end should remain as it is.

Input: lists = 1->2->3->4->5, k = 2
Output: 2->1->4->3->5

Input: lists = 1->2->3->4->5, k = 3
Output: 3->2->1->4->5

Solution

package com.vc.hard;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class ReverseNodesInKGroup {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return head;

        //Count total number of elements in an input list
        int total = 0;
        ListNode current = head;
        while(current != null) {
            current = current.next;
            total++;
        }

        final ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode prev = dummyNode;
        current = prev.next;
        ListNode next = current.next;

        int i = 1;
        while(next != null) {

            //If number remaining element in an input list is less than number of element required to make a group to reverse then return the answer.
            if(total < k) return dummyNode.next;


            //When current element i completes a group our logic should stop reversing elements in a current group
            if(i % k == 0) {
                total -= k;
                prev = current;
                current = next;
                next = next.next;
            }
            else {
                current.next = next.next;
                next.next = prev.next;
                prev.next = next;
                next = current.next;
            }
            i++;
        }
        return dummyNode.next;
    }
}

Let's understand how to reverse singly linked list visually.

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

Time Complexity

O(N)
Where N is total number of elements in input list.

Space Complexity

O(1)