【一天一道Leetcode】旋转链表
01
题目描述
题目描述：
给你一个链表的头节点head，旋转链表，将链表每个节点向右移动k个位置。
示例1：
输入：head = [0,1,2], k = 2
输出：[1,2,0]提示：
1.链表中节点的数目在范围[0, 500]内
2.-100 <= Node.val <= 100
3.0 <= k <= 2 * 10^9
02
思路和方法
特殊情况的分析：我们在对链表进行操作时，应该首先考虑到几个问题。
1.链表长度不大于1时，此时链表长度为空或为1，不管怎么移动都还是原来的链表，此时直接输出链表。
2.当需要移动的次数k为0或者为链表长度n的倍数时，这时也是直接输出链表就好。
将链表连接成环：首先要计算链表的长度n，并找到链表的末尾节点，将该节点与头节点相连，这样就得到了一个闭合为环的链表。
找到新断开节点：闭合为环的链表后，我们需要根据链表移动的个数，找到我们需要断开的那个节点。
即((n−1)−(k%n)),最终将得到的新链表输出即可。
我们用代码表示为:
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
//对链表的特殊情况进行判断
if k == 0 or not head or not head.next:
return head
n = 1
cur = head
//计算链表长度n
while cur.next:
cur = cur.next
n += 1
//对链表移动的次数k是否为 链表长度n的倍数 进行判断，
//同时确定新断点的移动位置add
if (add := n - k % n) == n:
return head
//将链表链接成环
cur.next = head
//寻找新链表的新断点
while add:
cur = cur.next
add -= 1
ret = cur.next
cur.next = None
return ret本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-04-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录