Rotate List

Question

Given a list, rotate the list to the right by k places, where k is non-negative.

Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.

Solution

基本上 linkedlist 的問題大部分都是一個模子，next or next.next 指來指去，或者是透過 dummy 去做。特別要注意的就是 corner case。這題有兩個解法，一個是利用 swap 概念來做，另一個是把頭跟尾接起來

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;
}

if (head == null)
        return head;

    ListNode copyHead = head;

    int len = 1;
    while (copyHead.next != null) {
        copyHead = copyHead.next;
        len++;
    }

    copyHead.next = head;

    for (int i = len - k % len; i > 1; i--)
        head = head.next;

    copyHead = head.next;
    head.next = null;

    return copyHead;
}