Leetcode: Reverse Nodes in k-Group

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

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Understand the problem:
The problem is an extension of last problem, where now k is an input along with the linked list. Again, the solution needs to be in-place and only nodes itself may be changed.

Solution:
The basic idea is to iterate the linked list and increase a counter. If the counter equals to the times of k, we reverse the range of linked list. 

Code (Java):

/**
 * 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 (head == null || head.next == null || k == 1)
            return head;
        
        ListNode helper = new ListNode(0);
        helper.next = head;
        
        ListNode pre = helper;
        ListNode cur = head;
        
        int counter = 0;
        
        while (cur != null) {
            counter++;
            
            if (counter % k == 0) {
                pre = reverseRange(pre, cur.next);
                cur = pre.next;
            } else {
                cur = cur.next;
            }
        }
        
        return helper.next;
    }
    
    // Reverse the linked list from pre to end, exclusively
    private ListNode reverseRange(ListNode prev, ListNode end) {
        ListNode head = prev.next;
        ListNode curr = head.next;
        
        while (curr != end) {
            ListNode temp = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            
            curr = temp;
        }
        
        head.next = end;
        return head;
    }
}

Summary:
Take away message from this problem. Reversing the linked list in-place is very basic and important. Make sure you can do it with and without using a dummy head node. 

Update on 9/21/15:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k <= 1) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        
        ListNode prev = dummyNode;
        ListNode curr = head;
        
        int count = 0;
        while (curr != null) {
            count++;
            if (count % k != 0) {
                curr = curr.next;
            } else {
                ListNode next = curr.next;
                
                // Reverse the list
                curr.next = null;
                List<ListNode> result = reverseList(prev.next);
                
                prev.next = result.get(0);
                ListNode tail = result.get(1);
                tail.next = next;
                prev = tail;
                curr = next;
            }
        }
        
        return dummyNode.next;
    }
    
    private List<ListNode> reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode tail = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        List<ListNode> result = new ArrayList<>();
        result.add(prev);
        result.add(tail);
        
        return result;
        
    }
}