61. Rotate List
Tags: ‘Linked List’, ‘Two Pointers’
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2 Output: 4->5->1->2->3->NULL Explanation: rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4 Output:2->0->1->NULLExplanation: rotate 1 steps to the right: 2->0->1->NULL rotate 2 steps to the right: 1->2->0->NULL rotate 3 steps to the right:0->1->2->NULLrotate 4 steps to the right:2->0->1->NULL
Solution
Consider when k larger than length of list, so just let k = k % length
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) return head;
if (k <= 0) return head;
int n = findLength(head);
k = k % n;
if (k == 0) return head;
ListNode slow = head, fast = head;
for (int i = 0; i < k; i++) { // separate by n+1
fast = fast.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// Now slow should be just before KEY node, fast is at tail
ListNode newHead = slow.next;
fast.next = head;
slow.next = null;
return newHead;
}
private int findLength(ListNode n) {
if (n == null) return 0;
int l = 0;
while (n != null) {
l++;
n = n.next;
}
return l;
}
// Better: count length while incrementing fast. Increment fast and slow separately
public ListNode rotateRight(ListNode head, int n) {
if (head==null||head.next==null) return head;
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode fast=dummy,slow=dummy;
int i;
for (i=0;fast.next!=null;i++)//Get the total length
fast=fast.next;
for (int j=i-n%i;j>0;j--) //Get the i-n%i th node
slow=slow.next;
fast.next=dummy.next; //Do the rotation
dummy.next=slow.next;
slow.next=null;
return dummy.next;
}