Java 双向链表按 N 个节点旋转的程序

17 Mar 2025 | 4 分钟阅读

在此程序中，我们需要创建一个双向链表并将其旋转 n 个节点。这可以通过维护一个从头节点开始并遍历列表直到 current 指向第 n 个节点的指针来实现。将从头到第 n 个节点的列表移到尾节点之后。现在第 n 个节点将是列表的尾节点，而第 n 个节点之后的节点将是新的头节点。这里，n 必须始终大于 0 但小于列表的大小。

原始列表

Java 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 节点。
遍历列表直到 current 到达第 n 个节点。
Tail 的 next 将指向 head 节点。
将 current 之后的节点设为新的 head。Head 的 previous 将指向 null。
current 节点将成为列表的 tail。Tail 的 next 将指向 null。

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

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

程序

public class RotateList {

    //Represent a node of the doubly linked list

    class Node{
        int data;
        Node previous;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    int size = 0;
    //Represent the head and tail of the doubly linked list
    Node head, tail = null;

    //addNode() will add a node to the list
    public void addNode(int data) {
        //Create a new node
        Node newNode = new Node(data);

        //If list is empty
        if(head == null) {
            //Both head and tail will point to newNode
            head = tail = newNode;
            //head's previous will point to null
            head.previous = null;
            //tail's next will point to null, as it is the last node of the list
            tail.next = null;
        }
        else {
            //newNode will be added after tail such that tail's next will point to newNode
            tail.next = newNode;
            //newNode's previous will point to tail
            newNode.previous = tail;
            //newNode will become new tail
            tail = newNode;
            //As it is last node, tail's next will point to null
            tail.next = null;
        }
        //Size will count the number of nodes present in the list
        size++;
    }

    //rotateList() will rotate the list by given n nodes
    public void rotateList(int n) {
        //Initially, current will point to head
        Node current = head;

        //n should not be 0 or greater than or equal to number of nodes present in the list
        if(n == 0 || n >= size)
            return;
        else {
            //Traverse through the list till current point to nth node
            //after this loop, current will point to nth node
            for(int i = 1; i < n; i++)
                current = current.next;

            //Now to move entire list from head to nth node and add it after tail
            tail.next = head;
            //Node next to nth node will be new head
            head = current.next;
            //Previous node to head should be null
            head.previous = null;
            //nth node will become new tail of the list
            tail = current;
            //tail's next will point to null
            tail.next = null;
        }
    }

    //display() will print out the nodes of the list
    public void display() {
        //Node current will point to head
        Node current = head;
        if(head == null) {
            System.out.println("List is empty");
            return;
        }
        while(current != null) {
            //Prints each node by incrementing the pointer.

            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {

        RotateList dList = new RotateList();
        //Add nodes to the list
        dList.addNode(1);
        dList.addNode(2);
        dList.addNode(3);
        dList.addNode(4);
        dList.addNode(5);

        System.out.println("Original List: ");
        dList.display();

        //Rotates list by 3 nodes
        dList.rotateList(3);

        System.out.println("Updated List: ");
        dList.display();
    }
}

输出

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

下一个主题Java 程序

Java 双向链表按 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

Java 程序

Java 双向链表按 N 个节点旋转的程序

算法

程序

相关帖子

Java 判断给定矩阵是否为单位矩阵的程序

Java 计算给定文本文件中单词数的程序

在控制台上打印以下图案的 Java 程序

Java 中数组中的倒序计数

Java 判断单链表是否为回文的程序

Java 查找字符串所有排列的程序

如何在 Java 中将 char 转换为字符串

查找字符串中重复字符的 Java 程序

在控制台上打印以下图案的 Java 程序 10

判断两个矩阵是否相等的 Java 程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器