LeetCode 61：旋转链表 Rotate List

Hwg 发布于2019-07-31 11:30 / 649人阅读

摘要：给定一个链表，旋转链表，将链表每个节点向右移动个位置，其中是非负数。按上述思路解，与旋转数组那道题大同小异，来介绍另一种很简单高效的方法。只需在第个节点之后切断，首尾连接即可。另外可能大于链表长度，应当做求余运算。

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

Given a linked list, rotate the list to the right by k places, where k is non-negative.

示例 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

解题思路：

如果你看过上周的文章：LeetCode 189：旋转数组，和本篇文章旋转链表除了承载数据的结构变了，其他都一样，简单说一下

不断反转特定长度数组：

输入:1->2->3->4->5反转整个数组: 5->4->3->2->1
拆分链表前k位为一段：5->4 , 3->2->1
反转前k位：4->5
反转剩余的:1->2->3
连接并输出: 4->5->1->2->3

按照这个思路，只需三次反转链表即可，而反转链表我们已经在文章 LeetCode 206：反转链表中已经详细的介绍过了，用了迭代、递归两种方法，所以按照上述解该题的方法也可以用两种方法实现。

按上述思路解，与旋转数组那道题大同小异，来介绍另一种很简单高效的方法。

观察输入输出：

输入：1->2->3->4->5，k=2
输出：4->5->1->2->3在节点3后切断链表：1->2->3，4->5
将头节点连接到尾节点：4->5->1->2->3
输出：4->5->1->2->3

得益于链表的特性，明显这种方式更简单，而节点3的位置刚好就是 len-k (len为链表长度)。只需在第 len-k 个节点之后切断，首尾连接即可。

另外 k 可能大于链表长度，应当做求余运算 k=k%len 。考虑到切断的节点位置可能是最后一个节点，或者是位置 0 (即头节点前)，明显不用做切断节点，但是按上述操作就会出现指针溢出报错，可以率先将首尾节点相连，组成环形链表。

Java：

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        int len = 1;
        ListNode cur = head;
        while (cur.next != null) {//计算链表长度
            cur = cur.next;
            len++;
        }
        cur.next = head;
        int mod = len - k % len;//切断节点的位置
        cur = head;
        while (--mod > 0) cur = cur.next;//找到切断节点
        ListNode newHead = cur.next;//新链表头节点
        cur.next = null;//切断
        return newHead;
    }
}

Python3：

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next or not k: return head
        cur = head
        len = 1
        while cur.next:
            len += 1
            cur = cur.next
        cur.next = head
        cur = head
        mod = len - k % len
        while mod - 1 > 0:
            cur = cur.next
            mod -= 1
        newHead = cur.next
        cur.next = None
        return newHead

欢迎关注微.信公.众号一起学习：爱写Bug

GPU云服务器云服务器旋转-rotate C语言数据结构旋转链表 Rotate LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/45239.html

[Leetcode] Rotate List 旋转链表

摘要：不过，由于可能大于链表的长度，所以我们要先对取链表长度的模。代码计算链表长度如果不旋转或者原链表为空则直接返回让快指针先走步找到新头节点的前一个节点将后半部分放到前面来 Rotate List Given a list, rotate the list to the right by k places, where k is non-negative. For example: Gi...

Yu_Huang 2019-08-14 12:40 评论0 收藏0
【Leetcode】61.旋转链表

摘要：小米广告第三代广告引擎的设计者开发者负责小米应用商店日历开屏广告业务线研发主导小米广告引擎多个模块重构关注推荐搜索广告领域相关知识给定一个链表，旋转链表，将链表每个节点向右移动个位置，其中是非负数。作者: 码蹄疾毕业于哈尔滨工业大学。小米广告第三代广告引擎的设计者、开发者；负责小米应用商店、日历、开屏广告业务线研发；主导小米广告引擎多个模块重构；关注推荐、搜索、广告领域相关知识; ...

Jeffrrey 2019-08-19 11:06 评论0 收藏0
【Leetcode】61.旋转链表

摘要：小米广告第三代广告引擎的设计者开发者负责小米应用商店日历开屏广告业务线研发主导小米广告引擎多个模块重构关注推荐搜索广告领域相关知识给定一个链表，旋转链表，将链表每个节点向右移动个位置，其中是非负数。作者: 码蹄疾毕业于哈尔滨工业大学。小米广告第三代广告引擎的设计者、开发者；负责小米应用商店、日历、开屏广告业务线研发；主导小米广告引擎多个模块重构；关注推荐、搜索、广告领域相关知识; ...

imtianx 2019-07-25 14:27 评论0 收藏0
【Leetcode】61.旋转链表

摘要：小米广告第三代广告引擎的设计者开发者负责小米应用商店日历开屏广告业务线研发主导小米广告引擎多个模块重构关注推荐搜索广告领域相关知识给定一个链表，旋转链表，将链表每个节点向右移动个位置，其中是非负数。作者: 码蹄疾毕业于哈尔滨工业大学。小米广告第三代广告引擎的设计者、开发者；负责小米应用商店、日历、开屏广告业务线研发；主导小米广告引擎多个模块重构；关注推荐、搜索、广告领域相关知识; ...

xushaojieaaa 2019-07-30 17:44 评论0 收藏0