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) {
		ListNode temp = head;
		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;
		return reverseList(head, k);
	}

	private ListNode reverseList(ListNode head, int length) {

        ListNode prev = null;
        ListNode first = head;
        ListNode temp = null;
        int i = length;
        if(length == 0)
            return head;
         //reverse k elements   
        while(i-- > 0 && head != null) {
            temp = head.next;
           head.next = prev;
           prev = head;
           head = temp;
        }
        // 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;
	ListNode start = head;
	//traverse till the end of the list and keep incrementing
	//count
	while (head.next != null) {
		head = head.next;
		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	
	head.next = start;
	//traverse for new k value		
	while (k-- > 0) {
		head = head.next;
	}
	// note: head is not the last element, so set the start.
	start = head.next;
	head.next = null;
	return start;

Subscribe to get latest updates.

© 2016 Java Questions | Sitemap