61. 旋转链表

本题来自 LeetCode：61. 旋转链表^[1]

题目描述

给定一个链表，旋转链表，将链表每个节点向右移动  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

题目分析

本题需要将链表向右移动 k 步，而不确定 k和链表长度 n的大小，故需要先将 n求出。在统计链表长度的过程中，可以先记录链表的尾节点，方便后续如果需要旋转链表时使用。比如示例 1 中， k = 2。

head                       tail
1  -  2  -  3  -  4  -  5  -  NULL

我们可以先找到原链表的尾节点 tail。这个时候可以直接将首尾节点连接起来，这时整个链表是个首尾相连的循环链表。

head                       tail    连接到头节点
1  -  2  -  3  -  4  -  5  -  1....

接下来只需将 3-4之间的连接断开即可。然后返回头节点

           preHead  head
1  -  2  -  3  -  4  -  5  -  1...
           preHead                  head
1  -  2  -  3  - NULL    4  -  5  -  1...
head
4  -  5  -  1  - 2  - 3  - NULL

题目解答

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null) {
            return null;
        }
        // 记录链表长度
        int n = 1;
        // 记录链表尾节点
        ListNode tail = head;
        // 找到原链表的尾节点
        while(tail.next != null) {
            n ++;
            tail = tail.next;
        }
        // 实际右移k个位置
        k = k % n;
        // 表示不移动
        if(k == 0) {
            return head;
        }
        // 执行到这里，表示一定会旋转链表了
        // 直接将头节点连接到尾节点上
        tail.next = head;

        // 记录实际头节点前一个节点，方便下面进行剪短处理
        ListNode preNode = head;
        // 记录需要多少步找到 实际头节点前一个节点
        int step = n - k - 1;
        // 找到preNode的位置
        while(step != 0) {
            step --;
            preNode = preNode.next;
        }
        // 找到实际头节点
        head = preNode.next;
        // 将需要旋转的那个节点剪端
        preNode.next = null;

        return head;
    }
}

复杂度分析：
时间复杂度： O(n)
空间复杂度： O(1)

参考资料

61. 旋转链表: https://leetcode-cn.com/problems/rotate-list

原文始发于微信公众号（xiaogan的技术博客）：