61. Rotate List

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

1
2
3
4
5
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:

1
2
3
4
5
6
7
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
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->NULL
rotate 4 steps to the right: 2->0->1->NULL
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k==0){
            return head;
        }
        ListNode cur = head, pre = null;
        int count = 0;
        while(cur!=null){
            pre = cur;
            cur = cur.next;
            count++;
        }
        pre.next = head;
        k %= count;
        int left = count-k;
        cur = head;
        while(left>0){
            pre = cur;
            cur = cur.next;
            left--;
        }
        pre.next = null;
        return cur;
    }
}

旋转链表题: - 先连成环;再走到起点;把终点断开 - 连成环是一种新的基本思想 - 如果需要使用某一位置之前的一个指针时,可以在while循环里用pre=cur来记录,然后让cur自增