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;
    }
}