Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Constraints:

  • The number of nodes in the list is n.
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

SOLUTION

public class ReverseNodesInKGroup {

    public ListNode reverseKGroup(ListNode head, int k) {
        // Base condition
        if (head == null || k == 1) {
            return head;
        }
        // Dummy node before head
        ListNode dummy = new ListNode(-1);
        // Point the next of this dummy to the current head
        dummy.next = head;
        // Node to keep track of the previous node
        ListNode previous = dummy;
        // Variable to keep count of the nodes in the linked list
        int count = 0;
        // Reference to the head which will be used to traverse
        ListNode current = head;
        while (current != null) {
            count++;
            if (count % k == 0) {
                previous = reverse(previous, current.next);
                current = previous.next;
            } else {
                current = current.next;
            }
        }
        return dummy.next;
    }

    private ListNode reverse(ListNode start, ListNode end) {
        // Previous node of the current node
        ListNode previous = start.next;
        // Current node
        ListNode current = previous.next;
        // Next node of the current node
        ListNode next;
        // Loop for the whole interval
        while (current != end) {
            // Next node of the current node
            next = current.next;
            // Next of current will point to the previous
            current.next = start.next;
            // Current node will become the previous node
            start.next = current;
            // Move pointer ahead
            current = next;
        }
        previous.next = end;
        // Return head node of the reversed linked list
        return previous;
    }
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro