Saturday, December 20, 2014

Rotate List

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.
I thought this problem was pretty easy. But it took me more than 30 minutes to finish it. The problem is, I forgot n can be any length, so I need to let n = n % length first. Moreover, in the case where n == length, there is nothing to rotate and we simply return the head.




public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }
 
public class RotateList {
    public ListNode rotateRight(ListNode head, int n) {
        if (head == null || n <= 0)
            return head;
        ListNode dummy = new ListNode(0);
        int length = findLength(head);
        n = n % length;
        if (n == 0)
            return head;
        ListNode node = head;
        int index = 0;
        while (node != null && index < length - n - 1)
        {
            node = node.next;
            index++;
        }
        dummy.next = node.next;
        node.next = null;
        node = dummy.next;
        while(node.next != null)
            node = node.next;
        node.next = head;
        return dummy.next;
        
    }
    private int findLength(ListNode head)
    {
        int length = 0;
        while (head != null)
        {
            length++;
            head = head.next;
        }
        return length;
    }
}

No comments:

Post a Comment