61. Rotate List

题目描述

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

For example:
Given1->2->3->4->5->NULLandk=2,
return4->5->1->2->3->NULL.

解题方法

Note:

1. 先確定把cycle移掉再移動
2. 使用兩個指針去紀錄newHead, newTail

//Using two pointers
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length ++;
            head = head.next;
        }
        return length;
    }

    public ListNode rotateRight(ListNode head, int n) {
        if( head == null || head.next == null){return head;}

        //preprocessing cycles
        int count = getLength(head);
        count = n % count;

        ListNode newHead = head;
        ListNode newTail = head;
        for(int i = 0; i< count; i++){
            newHead = newHead.next;
        }

        while( newHead.next != null){
            newHead = newHead.next;
            newTail = newTail.next;
        }

        newHead.next = head;
        ListNode dummy = new ListNode(0);
        dummy.next = newTail.next;
        newTail.next = null;

        return dummy.next;
    }