Reverse a Doubly Linked List by Swapping Data in Java

2025年5月5日 | 阅读 3 分钟

给定一个双向链表，在不使用任何额外空间的情况下，要求就地反转该链表。

示例 1

输入

节点：1, 2, 3

输出

原始双向链表为 1 -> 2 -> 3

反转后的双向链表为 3 -> 2 -> 1

解释

第一次交换：1 ↔ 3

由于中间的节点 2 保持不变，反转后的链表为 3 -> 2 -> 1。

示例 2

输入

节点：100

输出

原始双向链表为 100

反转后的双向链表为 100

解释

只有一个节点的链表反转后保持不变。

示例 3

输入

节点：15, 25, 5

输出

原始双向链表为 15 -> 25 -> 5

反转后的双向链表为 5 -> 25 -> 15

解释

第一次交换：15 ↔ 5

由于中间的节点 25 保持不变，反转后的链表为 5 -> 25 -> 15。

注意：空链表反转后保持不变。

双向链表允许我们向前和向后遍历，因为它同时具有前一个指针和后一个指针。因此，通过在链表开头放置一个指针（我们称之为左指针），在结尾放置一个右指针，我们可以将这两个指针向中间移动，将左指针向前移动，将右指针向后移动。

双向链表由代码定义，其中 prev_node 和 next_node 指针分别用于前向和后向遍历，每个节点包含整数数据。newNode() 方法使用空指针和提供的数据生成节点。insert() 方法通过更新新节点和现有头节点的指针来将一个节点添加到链表头部。reverseList() 函数通过在链表开头和结尾处对称位置的节点之间交换数据来反转链表，直到指针相遇或交叉。

实施

文件名： DoublyLinkedList.java

import java.util.*;
import java.io.*;
public class ReverseListSwapping
{
    // creating a node
    static class Node
    { 
    	int data; 
    	Node prev_node, next_node; 
    }; 
    // Function to add the given value to a new node
    static Node newNode(int value) 
    { 
    	Node temp = new Node(); 
    	temp.data = value; 
    	// Initialize the pointers to null
    	temp.prev_node = temp.next_node = null; 
    	return temp; 
    } 
    static void printList(Node head) 
    { 
        // Go through the list to the final node.
    	while (head.next_node != null)
    	{ 
    		System.out.print(head.data+ " <--> "); 
    		head = head.next_node; 
    	} 
    	System.out.println( head.data ); 
    } 
    // Insert a new node at the head of the list 
    static Node insert(Node head, int value) 
    { 
        // Create a new node with the supplied value.
    	Node temp = newNode(value); 
    	temp.next_node = head; 
    	// Update the old pointer to the new node in the current head.
    	(head).prev_node = temp; 
    	(head) = temp;
    	return head;
    } 
    static Node reverseList(Node head) 
    { 
    	Node left = head, right = head; 
    	// Move over the list and set the 
    	// right pointer to the list's end. 
    	while (right.next_node != null) 
    		right = right.next_node; 
    	// Swap the left and right pointer data, then move
    	// them in the direction of one another 
    	// until they cross or meet. 
    	while (left != right && left.prev_node != right)
    	{ 
    	    // Switch the left and right pointer data. 
    		int t = left.data;
    		left.data = right.data;
    		right.data = t;
    		left = left.next_node; 
    		right = right.prev_node; 
    	} 
    	return head;
    } 
    public static void main(String args[])
    { 
    	Node head = newNode(5); 
    	head = insert(head, 4); 
    	head = insert(head, 3); 
    	head = insert(head, 2); 
    	head = insert(head, 1);
    	System.out.println("The list before reversing is: ");
    	printList(head); 
    	System.out.println("The List After Reversing is :"); 
    	head=reverseList(head); 
    	printList(head); 
    
    }
}   

输出

 
The list before reversing is: 
1 <--> 2 <--> 3 <--> 4 <--> 5
The List After Reversing is :
5 <--> 4 <--> 3 <--> 2 <--> 1

下一主题Buzz Number Java

Reverse a Doubly Linked List by Swapping Data in Java

注意：空链表反转后保持不变。

实施

联系信息

关注我们

教程

面试题

在线编译器

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 Conversion

Java Misc

Reverse a Doubly Linked List by Swapping Data in Java

注意：空链表反转后保持不变。

实施

相关帖子

Java ME

How to Encrypt Password in Java

在 Java 中不使用函数查找字符串长度

Java 编程要素

Java 中的杂项运算符

Java Program to Find Sum of Natural Numbers

Cyclic Barrier Multithreading Java

设计 Java 中的自动售货机

Java DOM

Java 中不使用额外空间合并两个排序数组

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器