题目描述

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

样例

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL


示例 2:

输入: 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

解题思路

func rotateRight(head *ListNode, k int) *ListNode {
    if head==nil || k==0{
        return head
    }
    // 统计链表长度，并获取最后一个节点
    tail:=head
    cnt:=0
    for p:=head;p!=nil;p=p.Next{
        tail=p
        cnt++
    }
    // 构造成循环链表
    phead:=head
    tail.Next=head
    // 去掉循环移动的次数
    k=k%cnt
    // 转换成向左移动
    m:=cnt-k
    pre:=tail
    // 遍历链表
    for i:=0;i<m;i++{
        pre=pre.Next
        phead=phead.Next
    }
    // 断开链表
    pre.Next=nil
    return phead
}