旋转链表

问题陈述

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

1
2
3
4
5
6
7
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释://每次右旋，相当于把末尾元素移到前面来。
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

思路分析

我们的直觉是先把链表闭合成环，然后找到相应的位置断开，确定新的头尾。

新的链表头位置：(n - k % n)

新的链表尾位置：(n - k % n - 1)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution{
    public ListNode rotateRight(ListNode head,int k){
        if(head==null) return null;
        if(head.next==null) return head;
        //闭合成环
        ListNode node=head;
        int len;
        for(len=1;node.next!=null;len++){
            node=node.next;
        }
        node.next=head;
        //找到新的头节点
        ListNode newtail=head;
        for(int i=0;i<len-k%len-1;i++){//获取新头结点的前一个结点，即断开后的尾结点。
            newtail=newtail.next;
        }
        ListNode newhead=newtail.next;
        //断环
        newtail.next=null;
        return newhead;
    }
}