14. Python 程序按 N 个节点旋转双向链表。

17 Mar 2025 | 4 分钟阅读

在此程序中，我们需要创建一个双向链表，并将其旋转 n 个节点。这可以通过维护一个从头节点开始并遍历列表直到当前节点指向第 n 个节点的指针来实现。将列表从头节点移动到第 n 个节点，并将其放置在尾部之后。现在第 n 个节点将成为列表的尾部，并且第 n 个节点之后的节点将成为新的头部。这里，n 应该始终大于 0 但小于列表的大小。

原始列表

Python program to rotate doubly linked list by N nodes

旋转 3 个节点后的列表

在上面的示例中，我们需要旋转列表 3 个节点。首先，我们遍历列表直到 current 指向第 3 个节点，在本例中是节点 3。将从节点 1 到 3 的列表移到尾节点之后。现在，节点 4 将成为新的头节点，节点 3 将成为新的尾节点。

算法

定义一个 Node 类，它表示列表中的一个节点。它将有三个属性：数据、previous 指向前一个节点，以及 next 指向下一个节点。
为创建双向链表定义另一个类，它有两个节点：head 和 tail。最初，head 和 tail 将指向 null。
addNode() 将向列表中添加节点。

它首先检查头节点是否为 null，然后将节点作为头节点插入。
头节点和尾节点都将指向新添加的节点。
头节点的前一个指针将指向 null，尾节点的下一个指针将指向 null。
如果头节点不为 null，则新节点将插入到列表的末尾，使得新节点的前一个指针将指向尾节点。
新节点将成为新的尾节点。尾节点的下一个指针将指向 null。

a. rotateList() 将按给定的 n 个节点旋转列表。

首先，检查 n 是否为 0 或大于等于列表中存在的节点数。
如果是，则按原样打印列表。
否则，定义一个指向 head 的 current 节点。
迭代遍历列表，直到当前节点到达第 n 个节点。
Tail 的 next 将指向 head 节点。
将 current 之后的节点设为新的 head。Head 的 previous 将指向 null。
current 节点将成为列表的 tail。Tail 的 next 将指向 null。

a. display() 将显示列表中存在的所有节点。

定义一个新节点“current”，它将指向头节点。
打印 current.data 直到 current 指向 null。
在每次迭代中，current 将指向列表中的下一个节点。

程序

#Represent a node of doubly linked list  
class Node:  
    def __init__(self,data):  
        self.data = data;  
        self.previous = None;  
        self.next = None;  
          
class RotateList:  
    #Represent the head and tail of the doubly linked list  
    def __init__(self):  
        self.head = None;  
        self.tail = None;  
        self.size = 0;  
          
    #addNode() will add a node to the list  
    def addNode(self, data):  
        #Create a new node  
        newNode = Node(data);  
          
        #If list is empty  
        if(self.head == None):  
            #Both head and tail will point to newNode  
            self.head = self.tail = newNode;  
            #head's previous will point to None  
            self.head.previous = None;  
            #tail's next will point to None, as it is the last node of the list  
            self.tail.next = None;  
        else:  
            #newNode will be added after tail such that tail's next will point to newNode  
            self.tail.next = newNode;  
            #newNode's previous will point to tail  
            newNode.previous = self.tail;  
            #newNode will become new tail  
            self.tail = newNode;  
            #As it is last node, tail's next will point to None  
            self.tail.next = None;  
        #Size will count the number of nodes present in the list  
        self.size = self.size + 1;  
          
    #rotateList() will rotate the list by given n nodes  
    def rotateList(self, n):  
        #Initially, current will point to head  
        current = self.head;  
          
        #n should not be 0 or greater than or equal to number of nodes present in the list  
        if(n == 0 or n >= self.size):  
            return;  
        else:  
            #Traverse through the list till current point to nth node  
            #after this loop, current will point to nth node  
            for i in range(1, n):  
                current = current.next;  
                  
            #Now to move entire list from head to nth node and add it after tail  
            self.tail.next = self.head;  
            #Node next to nth node will be new head  
            self.head = current.next;  
            #Previous node to head should be None  
            self.head.previous = None;  
            #nth node will become new tail of the list  
            self.tail = current;  
            #tail's next will point to None  
            self.tail.next = None;  
              
    #display() will print out the nodes of the list  
    def display(self):  
        #Node current will point to head  
        current = self.head;  
        if(self.head == None):  
            print("List is empty");  
            return;  
              
        while(current != None):  
            #Prints each node by incrementing pointer.  
            print(current.data),  
            current = current.next;  
        print();  
          
dList = RotateList();  
#Add nodes to the list  
dList.addNode(1);  
dList.addNode(2);  
dList.addNode(3);  
dList.addNode(4);  
dList.addNode(5);  
   
print("Original List: ");  
dList.display();  
   
#Rotates list by 3 nodes  
dList.rotateList(3);  
   
print("Updated List: ");  
dList.display(); 

输出

Original List: 
1 2 3 4 5 
Updated List: 
4 5 1 2 3

下一个主题Python 程序

← 上一个下一个 →

14. Python 程序按 N 个节点旋转双向链表。

算法

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 程序

14. Python 程序按 N 个节点旋转双向链表。

算法

程序

相关帖子

Python 程序

Python 程序打印 1 到 100 之间的所有 Happy Numbers

Python 程序在循环链表末尾插入一个新节点

Python 程序制作一个简单的计算器

Python 程序创建并显示双向链表

Python 程序检查给定的数字是否为 Disarium 数

Python 程序打印区间内的所有素数

Python 程序逆序打印数组的元素

Python 程序打印数组中的最大元素

Python 程序打印数组中偶数位置的元素

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器