Reverse Nodes in k-Group

This problem is almost the same as the reverse linked list question. The only trick is you need to step from the head k-1 times to get to tail, then reverse the linked list from head to tail. If during the stepping you hit the null, then dont reverse and return.

Reverse singly linked list can be wrapped in one function. Notice that java passes reference by value, so head and tail passed into the function can not be changed inside the function. Also using a helper to deal with the pointer that points to the head. Just remember all the head and tail positions carefully.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 0 || k == 1 || head == null || head.next == null)
            return head;
        ListNode helper = new ListNode(0);
        helper.next = head;
        ListNode H = helper; // store head location for return
        ListNode tail = head;
        while (true) {
            for(int i = 0; i < k-1; i++) {
                tail = tail.next;
                if (tail == null)
                    return H.next;
            }
            reverseNode(head, tail); // java pass by value, head and tail value does not change by the function
            ListNode temp = head;
            head = tail;
            tail = temp;
            helper.next = head;
            helper = tail;
            if (helper.next == null)
                return H.next;
            head = helper.next;
            tail = helper.next;
        }
    }
    
    public void reverseNode(ListNode head, ListNode tail){
        if (head == tail) {// only one nodes
            return;
        }
        ListNode nTail = head; // new tail is head
        ListNode next = head.next;
        while(next != tail) {
            ListNode temp = next;
            next = next.next;
            temp.next = nTail;
            nTail = temp;
        }
        head.next = next.next;
        next.next = nTail;
        return;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s