[LeetCode] – Dummy Node – Reverse Nodes in k-Group

Problem:

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

Method 1: 

1. Use helper method: reverse the nodes between the two edge nodes. (Do not include the two edge nodes)

For this method, we need for cursor. Cursor 1: front edge node; Cursor 2: end edge node; Cursor 3: last, always insert nodes before this node; Cursor 4: temp, iterate through the list and do the reversion operation.

2. Use a dummy node. Iterate through the list. Do reverse method once you got k nodes. If there is not enough k elements, just do nothing.

Code for Method 1:

/**
 * 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 || k == 1) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        int i = 0;

        while(head != null){ // once you have a dummy node, you don't need the head pointer. Make use of head pointer.
            i ++;
            if (i % k== 0 ){
                pre = reverseRange(pre, head.next);
                head = pre.next;
            }else{
                head = head.next;
            }
        }
        return dummy.next;
    }

    public ListNode reverseRange (ListNode front, ListNode end){
        if (front == end || front.next == end) return front;
        ListNode last = front.next;
        ListNode temp = last.next;

        while (temp != end){
            last.next = temp.next;
            temp.next = front.next;
            front.next = temp;
            temp = last.next;
        }
        return last;
    }
}

Method 2: 

Use recursion. Parameter: head, length, k

Base case: if the length is equal or smaller than k, than just reverse all the elements

Reduction: if the length is larger than k, reverse the first k elements and then do the same thing for the next (length – k ) elements.

Code for Method 2:

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
       return reverseK(head, k, getLength(head));
    }

    public ListNode reverseK(ListNode head, int k, int len){
       if (k == 1 || k > len || head == null) return head; // k == 1 and head == null is the edge case
       // the k > len is the base case;

       // reverse first k nodes

       ListNode dummy = new ListNode(0);
       dummy.next = head;
       ListNode pre = dummy;
       ListNode last = head;
       head = head.next;  // head represent every element that is going to be switched.
       int cnt = 1; // if switch n elements, you have to do n-1 times swap.

       while (cnt < k){
           cnt ++;
           last.next = head.next;
           head.next = pre.next;
           pre.next = head;
           head = last.next;
       }

       last.next = reverseK(last.next,k,len-k);
       return dummy.next;

    }

    public int getLength(ListNode head){
        int len = 0;
        while(head!=null){
            len++;
            head=head.next;
        }
        return len;
    }
}

This is actually not a typical recursion.