【一天一道Leetcode】旋转链表

看那个码农

共 2260字,需浏览 5分钟

 ·

2021-04-06 14:08


本篇推文共计2000个字,阅读时间约3分钟。



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,再见2020。


【秋招纪实录】一篇特别正经的【腾讯】求职经验分享


【一天一道Leetcode】删除排序链表的重复元素



☆ END ☆

你与世界

只差一个

公众号

浏览 16
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报