61. Rotate List.md

61. Rotate List

Problem

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.

tag:

• linkedlist
• two pointers

Solution

把链表后K个节点旋转到前面； 研究了半天才搞懂题意 :(

采用快慢指针

1. 定义两个指针p,q， 初始化分别指向dummyHead, 然后移动p,q开始旋转的位置和链表尾
注意k可能超出链表长度， 因此要对链表长度取余， 即p移动```len-k%len```步， 
dummyHead->1->2->3->4->5->null
                 ^     ^
                 |     |
                 p     q


2. 对链表进行旋转操作

表尾指向表头：     q-next = dummyHead->next;
表头指向新的表头： dummyHead->next = p->next;
新的表尾指向空：   p-next = null

dummyHead-4->5->1->2->3->null
             ^        ^ 
             |        |
             q        p

java

    public ListNode rotateRight(ListNode head, int k) {
        if(head==null) return head;
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode p=dummyHead,q=dummyHead;
        
        int len = 0;
        while(q.next!=null) {
            q = q.next;
            len++;
        }
        for(int i=0; i<len-k%len; i++) p = p.next;
        
        q.next = dummyHead.next;
        dummyHead.next = p.next;
        p.next=null;
        
        return dummyHead.next;
    }

go