题目描述
题目描述:
给你一个链表的头节点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
思路和方法
特殊情况的分析:我们在对链表进行操作时,应该首先考虑到几个问题。
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