No.61 旋转链表 (Medium)

题目描述

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例1：

示例2：

思路

从示例2可以看出，k可能大于链表长度size, 也就是说，例如size = 3， k = 4时，向右移动4步，等价于向右移动1步，即真正移动的距离为k % size。

1. 遍历链表，找到尾部tail以及算出链表长度size；
2. tail指向head，形成环；
3. 移动k个位置，即移动k % size 个位置，新的tail相当于往前移动了k % size个位置，从正向数的话，新的tail为head后面的第size - (k % size) - 1个结点。例如size = 7, k = 2，那么新的tail 是 7 往前移动2个位置，即5， 5 就是head往后移动 5 - 1的位置，
4. 第3步找到了新的tail, 即newTail, 新的head即newTail的下一个结点，即newHead = newTail.next;
5. 使得newTail.next指向null

代码

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // 空链表或者只有一个结点的链表
        if (head == null || head.next == null) {
            return head;
        }
        if (k == 0) {
            return head;
        }
        ListNode tail = head;
        // 因为tail和head指向同一个结点，此时链表长度为1
        int size = 1;
        // 这里不能判断tail == null, 因为tail == null时，tail = tail.next会报空指针异常
        // 建议画一个链表，更形象
        while (tail.next != null) {
            tail = tail.next;
            size++;
        }
        // 形成环
        tail.next = head;
        ListNode newTail = head;
        ListNode newHead = head;
        // 找到新的tail
        for (int i = 0; i < size - (k % size) - 1; i++) {
            newTail = newTail.next;
        }
        // 新的head
        // 因为最后要返回头结点，所以需要保存
        newHead = newTail.next;
        // 断开
        newTail.next = null;
        return newHead;
    }
}