LeetCode 61:旋转链表 Rotate List

简介: ​给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。Given a linked list, rotate the list to the right by k places, where k is non-negative.

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

目录
相关文章
|
11月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
118 1
|
11月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
146 0
Leetcode第21题(合并两个有序链表)
|
5月前
|
算法 Go
【LeetCode 热题100】23:合并 K 个升序链表(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 23——合并 K 个升序链表的两种解法:优先队列(最小堆)和分治合并。题目要求将多个已排序链表合并为一个升序链表。最小堆方法通过维护节点优先级快速选择最小值,;分治合并则采用归并思想两两合并链表。文章提供了 Go 语言实现代码,并对比分析两种方法的适用场景,帮助读者深入理解链表操作与算法设计。
174 10
|
11月前
|
机器学习/深度学习
Leetcode第48题(旋转图像)
这篇文章介绍了LeetCode第48题“旋转图像”的解题方法,通过原地修改二维矩阵实现图像的顺时针旋转90度。
93 0
Leetcode第48题(旋转图像)
|
11月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
91 0
Leetcode第三十三题(搜索旋转排序数组)
|
11月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
118 0
LeetCode第二十四题(两两交换链表中的节点)
|
11月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
112 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
11月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
228 0
|
11月前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
82 0
|
11月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
142 0