LeetCode-61-旋转链表

题目

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

示例 1：

img

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

img

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

题解

这一题我的解法时间复杂度打败100%，空间复杂度才5%，但是感觉还是一个很不错的解法，比较相对来讲，时间复杂度更重要一点。（叉腰.jpg）

思路很简单，遍历k次，每次把最后一个节点头插法放到第一个去就可以了。

那么就会遇到第一个问题，比如旋转20000次，超时啦！怎么解决呢？

也很简单，我们只要知道了链表长度，然后k = k % len即可！因为如果旋转了len次，相当于没有变！

怎么获得len呢？也简单，先遍历一遍好了。这样的时间复杂度也很优秀！

在处理的时候，最好还是在当前指针cur搞一个前指针curFront，再断最后一个节点的时候很方便！此外一个哑节点dummy可以在头插法的时候很简便！

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // 思路：遍历k次，每次把最后一个放到第一个去
        // 需要一个头节点 dummy
        ListNode dummy = new ListNode(-101, head);
        ListNode cur = head, curFront = dummy;
        if (head == null) {
            return null;
        }
        int num = 1;
        while (cur.next != null) {
            num++;
            cur = cur.next;
        }
        cur = head;
        k = k % num;
        while (k > 0) {
            if (cur.next == null) { // 到了最后一个节点的标记
                // 先保存当前节点，再断开，最后加到头去
                ListNode temp = new ListNode(cur.val, null);
                curFront.next = null;
                temp.next = dummy.next;
                dummy.next = temp;
                // 处理头节点
                cur = dummy.next;
                curFront = dummy;
                // 移动过一次之后，需要缩减k值
                k--;
            } else {    // 否则两者都往后调移动
                cur = cur.next;
                curFront = curFront.next;
            }
        }
        return dummy.next;
    }
}