Wednesday, January 22, 2014

Rotate List (Java)


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.

Solution: when see  an ListNode question, recursion, two pointers  and link head and tail are always common ways to considered about.

In this question, link head and tail is a good choice. First, use an extra reference to go from head to tail meanwhile count the length of this list. once we got the length and the tail , we can do two things, one is linked the tail with head, another is calculate k depend on given n and the length of list, k is how many nodes should be move right. k=len-n%len; After we finished these two things, 
we can place an preHead reference at tail and let it go next k steps, then preHead will be the point just ahead our target head. then return break the list here and return our target head.