目录

0061:旋转链表(★)

力扣第 61 题

题目

给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。

示例 1:

输入:head = [1,2,3,4,5], k = 2
输出:[4,5,1,2,3]

示例 2:

输入:head = [0,1,2], k = 4
输出:[2,0,1]

提示:

  • 链表中节点的数目在范围 [0, 500]
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 109

相似问题:

分析

  • 先找到表尾 tail 并计算出链表长度 n
  • 找到新表尾 p,是第 n - k % n 个元素
  • 从 p 断开,将前面部分接到 tail 后面即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return None
        dum = ListNode(next=head)
        tail,n = dum,0
        while tail.next:
            tail = tail.next
            n += 1
        p = dum
        for _ in range(n-k%n):
            p = p.next
        tail.next = dum.next
        dum.next = p.next
        p.next = None
        return dum.next

33 ms