# Leetcode: Given a list, rotate the list to the right by k places.

https://leetcode.com/problems/rotate-list

Consider example `1->2->3->4 ` rotate the list by 2. `3->4->1->2`.

I have explained two different approaches. Each method has code sample with comments to understand it easily.

The LinkedList for the example is singly. Here is how Node class looks like:

``````class Node {
int value;
protected Node next;

public Node(int value) {
this.value = value;
}

public int getValue() {
return value;
}
}
``````

Method 1. (more intutive)

``````public class RotateLinkedList {

public ListNode reverseKList(ListNode head, int k) {
int count =0;
while(temp !=null) {
count++;
temp = temp.next;
}
//if k is greater than the length of the list, the take a mod
k = k > count ? k%count:k;
}

private ListNode reverseList(ListNode head, int length) {

ListNode prev = null;
ListNode temp = null;
int i = length;
if(length == 0)
//reverse k elements
while(i-- > 0 && head != null) {
}
// now temp is pointing to k+1, call reverseList recursively
// first is the first element of k list, which will now be
// the last element of k list, since its reversed.
if(temp != null) {
first.next = reverseList(temp, length);
}
//prev is now the first element of the reversed list
return prev;
}

public static void main(String[] args) {
ListNode l = new ListNode(1);
ListNode l1 = new ListNode(2);
ListNode l2 = new ListNode(3);
ListNode l3 = new ListNode(4);
ListNode l4 = new ListNode(5);
l.next = l1;l1.next=l2;l2.next=l3;l3.next=l4;
System.out.println("Original List");
ListNode n = l;
while(n != null) {
System.out.print(n.val +" ");
n=n.next;
}
System.out.println("");
//reverse by k
n = new ReverseListK().reverseKGroup(l, 4);
System.out.println("New List: ");
while(n != null) {
System.out.print(n.val +" ");
n=n.next;
}
}
}

Output:
Original List
1 2 3 4 5
New List:
4 3 2 1 5
``````

Method 2

There is an easier and faster approach.

• Traverse the list till the end. Keep the counter for length n
• Connect the end of list to the start. Continue traversing from last element
• Continue traversing till `n-k`
• the `n-k` element will be the last element of new list , `n-k+1` will be the first element of the list
• traverse to `n-k+1` and set the next of `n-k` element to NULL
``````
public ListNode rotateRight(ListNode head, int k) {
int count = 0;
//traverse till the end of the list and keep incrementing
//count
count++;
}
count++;
// if k > count, do k%count, its an optimization. 2%5 == 12%5
k = k % count;
//find the new k
k = Math.abs(count - k);
if (k == 0)
return start;
//connect last element to start