算法题：使用递归反转双向链表

2021年4月24日13:24:35 发表评论 1,071 次浏览

本文概述

``Original Doubly linked list``
``Reversed Doubly linked list``

1)如果列表为空, 则返回

C ++

``````//C++ implementation to reverse a doubly
#include <bits/stdc++.h>
using namespace std;

//a node of the doubly linked list
struct Node {
int data;
Node *next, *prev;
};

//function to get a new node
Node* getNode( int data)
{
//allocate space
Node* new_node = new Node;
new_node->data = data;
new_node->next = new_node->prev = NULL;
return new_node;
}

//function to insert a node at the beginning
{
//since we are adding at the beginning, //prev is always NULL
new_node->prev = NULL;

//link the old list off the new node

//change prev of head node to new node

//move the head to point to the new node
}

//function to reverse a doubly linked list
Node* Reverse(Node* node)
{
//If empty list, return
if (!node)
return NULL;

//Otherwise, swap the next and prev
Node* temp = node->next;
node->next = node->prev;
node->prev = temp;

//If the prev is now NULL, the list
//has been fully reversed
if (!node->prev)
return node;

//Otherwise, keep going
return Reverse(node->prev);
}

//Function to print nodes in a given doubly
{
}
}

//Driver program to test above
int main()
{

cout <<"Original list: " ;

cout <<"\nReversed list: " ;
return 0;
}``````

Java

``````//Java implementation to reverse a doubly
class GFG
{

//a node of the doubly linked list
static class Node
{
int data;
Node next, prev;
};

//function to get a new node
static Node getNode( int data)
{
//allocate space
Node new_node = new Node();
new_node.data = data;
new_node.next = new_node.prev = null ;
return new_node;
}

//function to insert a node at the beginning
static Node push(Node head_ref, Node new_node)
{
//since we are adding at the beginning, //prev is always null
new_node.prev = null ;

//link the old list off the new node

//change prev of head node to new node

//move the head to point to the new node
}

//function to reverse a doubly linked list
static Node Reverse(Node node)
{
//If empty list, return
if (node == null )
return null ;

//Otherwise, swap the next and prev
Node temp = node.next;
node.next = node.prev;
node.prev = temp;

//If the prev is now null, the list
//has been fully reversed
if (node.prev == null )
return node;

//Otherwise, keep going
return Reverse(node.prev);
}

//Function to print nodes in a given doubly
{
{
System.out.print( head.data + " " );
}
}

//Driver code
public static void main(String args[])
{

System.out.print( "Original list: " );

System.out.print( "\nReversed list: " );
}
}

//This code is contributed by Arnab Kundu``````

Python3

``````# Python3 implementation to reverse a doubly
import math

# a node of the doubly linked list
class Node:
def __init__( self , data):
self .data = data
self . next = None

# function to get a new node
def getNode(data):

# allocate space
new_node = Node(data)
new_node.data = data
new_node. next = new_node.prev = None
return new_node

# function to insert a node at the beginning
# of the Doubly Linked List

# since we are adding at the beginning, # prev is always None
new_node.prev = None

# link the old list off the new node

# change prev of head node to new node
if (head_ref ! = None ):

# move the head to point to the new node

# function to reverse a doubly linked list
def Reverse(node):

# If empty list, return
if not node:
return None

# Otherwise, swap the next and prev
temp = node. next
node. next = node.prev
node.prev = temp

# If the prev is now None, the list
# has been fully reversed
if not node.prev:
return node

# Otherwise, keep going
return Reverse(node.prev)

# Function to print nodes in a given doubly
while (head ! = None ) :
print (head.data, end = " " )

# Driver Code
if __name__ = = '__main__' :

# Create doubly linked: 10<.8<.4<.2 */
print ( "Original list: " , end = "")

print ( "\nReversed list: " , end = "")

# This code is contributed by Srathore``````

C#

``````//C# implementation to reverse a doubly
using System;

class GFG
{

//a node of the doubly linked list
public class Node
{
public int data;
public Node next, prev;
};

//function to get a new node
static Node getNode( int data)
{
//allocate space
Node new_node = new Node();
new_node.data = data;
new_node.next = new_node.prev = null ;
return new_node;
}

//function to insert a node at the beginning
static Node push(Node head_ref, Node new_node)
{
//since we are adding at the beginning, //prev is always null
new_node.prev = null ;

//link the old list off the new node

//change prev of head node to new node

//move the head to point to the new node
}

//function to reverse a doubly linked list
static Node Reverse(Node node)
{
//If empty list, return
if (node == null )
return null ;

//Otherwise, swap the next and prev
Node temp = node.next;
node.next = node.prev;
node.prev = temp;

//If the prev is now null, the list
//has been fully reversed
if (node.prev == null )
return node;

//Otherwise, keep going
return Reverse(node.prev);
}

//Function to print nodes in a given doubly
{
{
Console.Write( head.data + " " );
}
}

//Driver code
public static void Main(String []argsS)
{

Console.Write( "Original list: " );

``````Original list: 10 8 4 2