Python 数据结构之旋转链表

简介

在进行链表操作时，有时需要旋转链表的一部分，即将链表的最后几个节点移到链表的头部。本文将讲解 Python 实现旋转链表的方法。

方法

我们需要了解两个概念：旋转链表、链表反转。

旋转链表

假设链表为1-2-3-4-5，k=2，将链表后两个节点移动到链表头部，即转化为4-5-1-2-3。

做法如下：

1. 先遍历链表，得出链表长度 n。
2. 计算旋转的位置，即计算出在第几个节点处将链表切开（分成两个链表），并将原链表的最后一个节点指向原链表头结点。
3. 再次遍历链表，将切开的两个链表分别反转。
4. 将反转后的前链表的尾结点指向反转后的后链表的头结点，即可得到最终链表。

链表反转

假设链表为1-2-3-4-5，反转后变为5-4-3-2-1。

做法如下：

1. 依次遍历链表，记录上一个节点和当前节点。
2. 将当前节点的 next 指向上一个节点。
3. 将上一个节点更新为当前节点，将当前节点往后移，继续遍历，直到结束。

代码示例

旋转链表

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next or k == 0:
            return head

        # 计算链表长度
        length = 1
        p = head
        while p.next:
            p = p.next
            length += 1

        # 计算旋转位置
        k %= length
        if k == 0:
            return head
        p.next = head # 首尾相连
        cut = length - k
        p = head
        for i in range(cut-1):
            p = p.next
        new_head = p.next
        p.next = None

        # 反转链表
        old_head = head
        new_head = self.reverseList(new_head)
        head = self.reverseList(old_head)
        old_head.next = new_head

        return head

    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        pre = None
        cur = head
        while cur:
            next_node = cur.next
            cur.next = pre
            pre = cur
            cur = next_node
        return pre

示例

示例1：

链表：1-2-3-4-5, k=2

旋转后链表：4-5-1-2-3

s = Solution()
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
k = 2
new_head = s.rotateRight(head, k)
while new_head:
    print(new_head.val)
    new_head = new_head.next

输出：

4
5
1
2
3

示例2：

链表：0-1-2, k=4

旋转后链表：2-0-1

s = Solution()
head = ListNode(0)
node1 = ListNode(1)
node2 = ListNode(2)
head.next = node1
node1.next = node2
k = 4
new_head = s.rotateRight(head, k)
while new_head:
    print(new_head.val)
    new_head = new_head.next

输出：

2
0
1

总结

本文详细介绍了 Python 实现旋转链表的方法，涉及到链表长度计算、链表反转、链表节点合并等知识点。同时给出了两个示例，希望能对大家有所帮助。