Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given
return
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.Given
1->2->3->4->5->NULL
and k = 2
,return
4->5->1->2->3->NULL
.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