Python数据结构之旋转链表(Python实现高效旋转链表详解)

原创

ithorizon 6个月前 (10-20) 阅读数 22 #后端开发

Python数据结构之旋转链表

一、旋转链表简介

旋转链表是一种特殊的链表操作，指的是将链表的头部元素移动到链表的尾部，或者将尾部元素移动到头部。这种操作通常用于实现一些特定的功能，如循环队列、音乐播放器的播放列表等。

二、链表基础知识回顾

在介绍旋转链表之前，我们先回顾一下链表的基本知识。链表是一种常见的基础数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。

三、旋转链表的实现

下面我们将详细介绍怎样使用Python实现一个高效的旋转链表。

3.1 定义链表节点类

首先，我们需要定义一个链表节点类，用于构建链表。


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

3.2 定义旋转链表类

接下来，我们定义一个旋转链表类，包含旋转操作和相关辅助方法。


class RotatedLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    def insert(self, value):
        new_node = ListNode(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1
    def rotate(self, k):
        if self.head is None or k % self.size == 0:
            return
        
        current = self.head
        count = 1
        while count < k % self.size:
            current = current.next
            count += 1
        new_head = current.next
        current.next = None
        self.tail.next = self.head
        self.head = new_head
        self.tail = current
    def display(self):
        current = self.head
        while current:
            print(current.value, end=" ")
            current = current.next
        print()

四、旋转链表的操作示例

下面通过一个示例来演示怎样使用旋转链表类。


# 创建旋转链表实例
rotated_list = RotatedLinkedList()
# 插入元素
rotated_list.insert(1)
rotated_list.insert(2)
rotated_list.insert(3)
rotated_list.insert(4)
rotated_list.insert(5)
# 显示原始链表
print("原始链表:")
rotated_list.display()
# 旋转链表
rotated_list.rotate(2)
# 显示旋转后的链表
print("旋转2次后的链表:")
rotated_list.display()