447，双指针解旋转链表

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

I figure life's a gift, and I don't intend on wasting it.

我觉得人生就是份礼物，而我不愿白白浪费。

问题描述

给定一个链表，旋转链表，将链表每个节点向右移动 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有可能比链表的长度还要大，所以先要计算链表的长度len，需要旋转的步数就是（k%len）。一种比较简单的方式就是先把链表连接成一个环，然后再把链表在某个合适的位置断开。

我们可以使用两个指针，一个快指针fast从头开始遍历直到走到链表的末尾，然后再把链表串成一个环形。还一个指针slow也是从头开始，走（len-k%len）步就是我们要返回的链表头，这里可能有点疑问，为什么不是走（k%len）步，这是因为我们需要把链表后面的（k%len）个移到前面，因为单向链表我们没法从后往前遍历，所以我们只能从前往后移动（len-k%len）步。但实际上操作的时候会少走一步，具体来举个例子看一下，这里就以示例1为例画个图来看一下

原理比较简单，来直接看下代码

 1public ListNode rotateRight(ListNode head, int k) {
 2    if (head == null)
 3        return head;
 4    ListNode fast = head, slow = head;
 5    //链表的长度
 6    int len = 1;
 7    //统计链表的长度，顺便找到链表的尾结点
 8    while (fast.next != null) {
 9        len++;
10        fast = fast.next;
11    }
12    //首尾相连，先构成环
13    fast.next = head;
14    //慢指针移动的步数
15    int step = len - k % len;
16    //移动步数，这里大于1实际上是少移了一步
17    while (step-- > 1) {
18        slow = slow.next;
19    }
20    //temp就是需要返回的结点
21    ListNode temp = slow.next;
22    //因为链表是环形的，slow就相当于尾结点了，
23    //直接让他的next等于空
24    slow.next = null;
25    return temp;
26}