[数据结构与算法]【LeetCode 61 单向链表专项】旋转链表

文章目录

• • 1. 题目
  • • 1.1 示例
    • 1.2 说明
    • 1.3 限制
  • 2. 解法一
  • • 2.1 分析
    • 2.2 解答
    • 2.3 复杂度

1. 题目

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

1.1 示例

• 示例 $1$ ：

  • 输入： head = [1, 2, 3, 4, 5] ， k = 2 ；
  • 输出： [4, 5, 1, 2, 3] 。

• 示例 $2$ ：

  • 输入： head = [0, 1, 2] ， k = 4 ；
  • 输出： [2, 0, 1] 。

1.2 说明

• 来源： 力扣（LeetCode）
• 链接： https://leetcode-cn.com/problems/rotate-list/

1.3 限制

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• $0\le \text{k}\le 2?10^9$

2. 解法一

2.1 分析

这里可以直接参考【LeetCode 20天「算法」刷题计划】旋转数组（189）中的第 $3$ 种解法，即直接将链表在倒数第 k 个（k = k % length ，其中 length 为链表长度）节点处分成两个部分，然后将倒数第 k 个节点作为新的头节点保存，接着将前半部分链接至后半部分的尾部，最后返回保存的倒数第 k 个节点。

然而，上述解答的问题在于，针对链表无法进行根据索引快速定位至倒数第 k 个节点，对此，可以参考【LeetCode 20天「算法」刷题计划】删除链表的倒数第 N 个结点（19）。

2.2 解答

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def _find_kth_from_tail(self, head: ListNode, k: int) -> ListNode:
        slow = fast = head
        for _ in range(k):
            fast = fast.next
        while fast.next:
            slow = slow.next
            fast = fast.next
        succ = slow.next
        slow.next = None
        return succ

    def rotate_right(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        length = 0
        cursor = head
        while cursor:
            length += 1
            cursor = cursor.next

        k = k % length
        if k == 0:
            return head
        
        rotated_head = self._find_kth_from_tail(head, k)
        cursor = rotated_head
        
        while cursor.next:
            cursor = cursor.next
        cursor.next = head
        return rotated_head

2.3 复杂度

• 时间复杂度： $O(n)$ ；
• 空间复杂度： $O(1)$ 。