61. Rotate List

题目描述

Given a list, rotate the list to the right by k places,

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

解题方法

1. 首先要確認linked list's length 與 n cycle的關係
2. 利用first/second two pointers: ＊＊＊先將first/second 指向dummy, 目的為指到目的的pre node (19題也是相同的做法)
3. first pointer先移動n步
4. first/second 同時移動到leaf node
5. 這時候second移動到n 的前一個node
6. 記得用dummy node 指到下個節點，然後將前一個節點的next指向null

    private int getLen(ListNode head){
        int len = 0;
        while(head != null){
            len++;
            head = head.next;
        }
        return len;
    }

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

        int cnt = getLen(head);
        n = n % cnt;
        if(n == 0){
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        for(int i = 0; i < n; i++){
            first = first.next;
        }

        while(first.next != null){
            first = first.next;
            second = second.next;
        }
        ListNode newHead = second.next;
        first.next = head;
        second.next = null;
        return newHead;
    }