Leetcode(61) Rotate List

发表于 | 更新于 | 分类于

Description:

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

Example 1:

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:

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

解法：

考虑到是移动链表题，而单向链表不太好进行回退操作，故考虑将其先变为循环链表，然后根据原链表的长度与移动的次数确定在哪个位置进行断开和指定谁为右移后的头指针。经过分析可得，从原始链表头指针往后走n- 1 - k % n个节点就到达新链表的头结点前一个点（n为链表长度）。具体实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) {
            return head;
        }
        int count = 0;
        ListNode tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
            count++;
        }
        tmp.next = head;
        tmp = head;
        for (int i = 1; i <= count - k % (count + 1); i++) {
            tmp = tmp.next;
        }
        head = tmp.next;
        tmp.next = null;
        return head;
    }
}