Given a list, rotate the list to the right by k places, where k is non-negative.

For example:

Given 1->2->3->4->5->NULL and k = 2,

return 4->5->1->2->3->NULL.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
  public ListNode rotateRight(ListNode head, int k) {
    
  }
}

This problem is selected from LeetCode.

Solution

Setup a fast pointer and a slow pointer. First move fast pointer k%length step, then move the fast pointer and slow pointer
together until the fast pointer gets to the tail. Then invert the two parts of the list.

public class Solution {
  public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null) 
      return head;
    
    k = k % getLen(head);
    if (k == 0) 
      return head;

    ListNode fast = head;
    for (int i = 0; i < k; i++) {
      fast = fast.next;
    }
    
    ListNode slow = head;
    while (fast.next != null) {
      fast = fast.next;
      slow = slow.next;
    }
    fast.next = head;
    head = slow.next;
    slow.next = null;
    
    return head;
  }
  
  private int getLen(ListNode node) {
    int len = 0;
    while (node != null) {
      node = node.next;
      len++;
    }
    
    return len;
  }
}

RelatedPost