Python中链表的旋转链表（Rotate List）操作

2023-04-11 00:00:00 操作链表旋转

旋转链表即将链表中的元素向右移动k个位置，其中k是非负数且小于链表长度。

我们可以先统计链表长度，并将链表首尾相接（形成一个环），然后向右移动k个位置，找到新的链表头和尾，将尾部断开即可。

下面是代码实现：

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

def rotateRight(head: ListNode, k: int) -> ListNode:
    if not head or k == 0:
        return head

    # 统计链表长度
    n = 1
    cur = head
    while cur.next:
        cur = cur.next
        n += 1

    # 将链表首尾相连
    cur.next = head

    # 找到新的链表头和尾
    k = k % n
    for _ in range(n-k):
        cur = cur.next
    new_head = cur.next

    # 断开尾部
    cur.next = None

    return new_head

我们可以使用以下链表作为范例：

1 -> 2 -> 3 -> 4 -> 5

如将其向右移动3个位置，结果应为：

3 -> 4 -> 5 -> 1 -> 2

我们可以使用以下代码进行测试：

# 构造链表
n5 = ListNode(5)
n4 = ListNode(4, n5)
n3 = ListNode(3, n4)
n2 = ListNode(2, n3)
n1 = ListNode(1, n2)

# 执行旋转操作
new_head = rotateRight(n1, 3)

# 检查结果
cur = new_head
while cur:
    print(cur.val, end=" ")
    cur = cur.next

输出:

3 4 5 1 2

注意，当链表长度为0或1时，不需要进行旋转。因此，我们需要添加以下代码进行特判：

if not head or k == 0:
    return head

相关文章