25. Reverse Nodes in k-Group.md

25. Reverse Nodes in k-Group

Question:

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.

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

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

Result:

• Reverse a single LinkedList:

public class Node {
	public static void main(String[] args) {
		ListNode<Integer> dummy = new ListNode<Integer>(0);
		ListNode<Integer> temp = dummy;
		for(int i = 1; i < 10; i++){
			temp.next = new ListNode<Integer>(i);
			temp = temp.next;
		}
		//Try to inverse the list.
		ListNode<Integer> pre = null;
		ListNode<Integer> node = dummy.next;
		while(node != null){
			ListNode<Integer> next = node.next;
			node.next = pre;
			pre = node;
			node = next;
		}
		int count = 0;
		while(pre != null && count < 20){
			System.out.print(pre.val + "	");
			pre = pre.next;
			count++;
		}
	}
	private static class ListNode<T>{
		ListNode<T> next;
		T val;
		public ListNode(T val) {this.val = val;}
	}
}

• Reverse Nodes in k-Group

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode curr = head;
        int count = 0;
        while(curr != null && count != k){
            count++;
            curr = curr.next;
        }
        if(count == k){
            curr = reverseKGroup(curr, k);
            while(count-- > 0){
                ListNode temp = head.next;
                head.next = curr;
                curr = head;
                head = temp;
            }
            head = curr;
        }
        return head;
    }
}

二刷

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int count = 0;
        ListNode cur = head;
        ListNode next = null;
        while(cur != null && count != k){
            count++;
            cur = cur.next;
        }
        if(k == count){
            cur = reverseKGroup(cur, k);
            while(count-- > 0){
                next = head.next;
                head.next = cur;
                cur = head;
                head = next;
            }
            head = cur;
        }
        return head;
    }
}

Amazon Session

• Method 1: Recursion

   /**
    * Definition for singly-linked list.
    * public class ListNode {
    *     int val;
    *     ListNode next;
    *     ListNode(int x) { val = x; }
    * }
    */
   class Solution {
   	public ListNode reverseKGroup(ListNode node, int k){
   		if(node == null) return null;
   		ListNode dummy = new ListNode(0);
   		dummy.next = node;
   		ListNode temp = dummy;
   		for(int i = 0; i < k; i++){
   			if(temp.next == null) return node;
   			temp = temp.next;
   		}
   		int count = 0;
   		ListNode pre = null, cur = node, next = null;
   		while(count++ < k && cur != null){
   			next = cur.next;
   			cur.next = pre;
   			pre = cur;
   			cur = next;
   		}
   		if(cur == null) return pre;
   		node.next = reverseKGroup(cur, k);
   		return pre;
   	}
   }