Reverse Nodes in k-Group

Published over 1 year ago, last updated over 1 year ago

Problem

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.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

Since constant memeory is required, we are not allowed to use recursion. Also, we don't know the relation between k and length of list. We might need a counter when we iterate the list.

Assume when can find at list one Kth node in the given list.

ListNode tail = head;
int count = 1;
while (tail != null && count < k) {
    tail = tail.next;
    count++;
}

If tail == null, the whole program ends.Otherwise, we get a part of the given list that need to be reversed.

Here is an example to reverse a part of the list given head and tail :

private void reverse(ListNode start, ListNode end) {
    ListNode pre = end.next;
    ListNode preRecord = pre;
    while (start != preRecord) {
        ListNode next = start.next;
        start.next = pre;
        pre = start;
        start = next;
    }
}

After calling this function, start becomes the tail of list (notice that there can be ListNodes linked after start) while end becomes the start of list.

As we have counter to find target part of list and reverse function to reverse it. We can run this procedure iteratively until tail is null.


Below is an example solution:



public class ReverseNodesInKGroup {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode res = null;
        ListNode preEnd = null;
        ListNode tail = head;
        ListNode start = head;
        while (tail != null) {
            int count = 1;
            while (tail != null && count < k) {
                tail = tail.next;
                count++;
            }
            if (tail == null) {
                return res == null ? head : res;
            }
            reverse(start, tail);
            if (res == null) {
                res = tail;
                preEnd = start;
            } else {
                preEnd.next = tail;
                preEnd = start;
            }
            start = start.next;
            tail = start;
        }
        return res;
    }

    private void reverse(ListNode start, ListNode end) {
        ListNode pre = end.next;
        ListNode preRecord = pre;
        while (start != preRecord) {
            ListNode next = start.next;
            start.next = pre;
            pre = start;
            start = next;
        }
    }
}


Reversing a list is much important when you are dealing with a singly linked list. Below is an example to reverse it all the way to the end. i.e We only know the head of list.

public ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

This function returns the new head of list.


Comments

    No comment yet



Leave your comment