【leetcode】旋转链表

Myth丶恋晨 2022-03-08 18:28 275阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]

--------------------

# 算法思路 #

1.  首先确定链表的长度，然后使用k对这个长度取余数，这样避免循环计算
2.  找到倒数第k个节点作为头结点
3.  一直往后遍历到None，连接到首节点
4.  将最后的节点置为None

其实有个更方便的办法：先将链表连接为循环链表（遍历链表长度的时候，就可以连接成循环链表）然后想办法从中间截断，不过时间复杂度是一样的

class Solution:
        def listLength(self, head):
            length = 0
            p = head
            while p:
                length += 1
                p = p.next
            return length
        def rotateRight(self, head: ListNode, k: int) -> ListNode:
            if head == None:
                return None
            k = k % (self.listLength(head))
            if k == 0:
                return head
            p = head
            for i in range(k):
                p = p.next
            newHead = head
            while p:
                p = p.next
                newHead = newHead.next
            p = newHead
            while p.next:
                p = p.next
            p.next = head
            p = head
            while p.next != newHead:
                p = p.next
            p.next = None
            return newHead

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220308/e8bec178d02a49de9f92ab2b21640bc0.png

发表评论取消回复

表情：

评论列表（有 0 条评论，275人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode:61.旋转链表

题目描述：给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。示例1：输入: 1->2->3->4->5->NULL,

亦凉/ 2023年07月10日 15:42/ 0 赞/ 4 阅读

相关 leetcode---61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。示例 1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4-

我就是我/ 2023年02月23日 08:15/ 0 赞/ 5 阅读

相关 LeetCode61. 旋转链表

难度：`中等` 题目描述：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 ![在这里插入图片描述][watermark_type_

叁歲伎倆/ 2022年11月13日 15:30/ 0 赞/ 183 阅读

相关 leetcode#61. 旋转链表

题目 https://leetcode-cn.com/problems/rotate-list/ 代码 / Definition for si

我会带着你远行/ 2022年11月13日 15:22/ 0 赞/ 122 阅读

相关 LeetCode 61. 旋转链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

矫情吗；*/ 2022年10月31日 12:25/ 0 赞/ 138 阅读

相关 LeetCode61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。示例 1: 输入: 1->2->3->4->5->NULL, k = 2

ゝ一世哀愁。/ 2022年05月13日 05:04/ 0 赞/ 167 阅读

相关【LeetCode】61. 旋转链表

题目链接：[https://leetcode-cn.com/problems/rotate-list/description/][https_leetcode-cn.com_p

待我称王封你为后i/ 2022年05月11日 11:20/ 0 赞/ 174 阅读

相关 leetcode:61. 旋转链表

题目: 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。示例 1: 输入: 1->2->3->4->5->NULL, k = 2

ゞ浴缸里的玫瑰/ 2022年04月05日 13:09/ 0 赞/ 194 阅读

相关【leetcode】旋转链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

Myth丶恋晨/ 2022年03月08日 18:28/ 0 赞/ 276 阅读

相关 Leetcode61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。示例 1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4-

川长思鸟来/ 2022年01月15日 04:01/ 0 赞/ 203 阅读