61. 旋转链表

题目描述

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

示例：

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

思路

1.首先我们可以遍历一次链表，获取链表的长度n。
2.我们可以将头结点移动 （n-k%n -1）次 获取后半部分的链表。
3.我们可以将后半部分连接的下一个结点保存起来，那便是前一部分的链表。
4.最后将前后两部分的链表拼接到一起即可。
5.注意将后半部分的链表尾部置空即可。

Java代码实现

   public ListNode rotateRight(ListNode head, int k) {
        //首先获取链表的长度
        ListNode p = head;
        int len = 0;
        while(head != null){
            len++;
            head = head.next;
        }
        //不需要移动链表，直接返回即可
        if(len == 0 || len == 1 || k == 0 || k%len == 0)
            return p;
        //头部需要移动的距离
        int tailDis = len-k%len-1;
        ListNode last = p;
        //后半部
        ListNode behind = last;
        while(tailDis>0){
            tailDis--;
            last = last.next;
        }
        ListNode front = last.next;
        ListNode res = front;
        //尾部链表置空
        last.next = null;
        //拼接链表
        while(front.next != null){
            front = front.next;
        }
        front.next = behind;

        return res;
    }

Golang代码实现

func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || k == 0{
        return head
    }
    len := 0

    p := head

    for p != nil {
        p = p.Next
        len++
    }

    if(len == 1 || k%len == 0){
        return head
    }

    step := len - k%len -1

    p = head
    tail := p

    for step>0 {
        p = p.Next
        step--
    }

    newHead := p.Next
    p.Next = nil

    p = newHead

    for p.Next != nil  {
        p = p.Next
    }
    p.Next = tail

    return newHead

}