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

本文概述

• C ++
• Java
• Python3
• C#

给定一个双向链表。使用递归将其反转。

Original Doubly linked list

Reversed Doubly linked list

我们已经讨论过>逆向双向链接列表的迭代解决方案

算法

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

2)通过交换head-> prev和head-> next来反转头部

3)如果prev = NULL, 则表示列表已完全反转。否则反转(head-> prev)

C ++

//C++ implementation to reverse a doubly
//linked list using recursion
#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
//of the Doubly Linked List
void 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
     new_node->next = (*head_ref);
  
     //change prev of head node to new node
     if ((*head_ref) != NULL)
         (*head_ref)->prev = new_node;
  
     //move the head to point to the new node
     (*head_ref) = 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
//linked list
void printList(Node* head)
{
     while (head != NULL) {
         cout <<head->data <<" " ;
         head = head->next;
     }
}
  
//Driver program to test above
int main()
{
     //Start with the empty list
     Node* head = NULL;
  
     //Create doubly linked: 10<->8<->4<->2 */
     push(&head, getNode(2));
     push(&head, getNode(4));
     push(&head, getNode(8));
     push(&head, getNode(10));
     cout <<"Original list: " ;
     printList(head);
  
     //Reverse doubly linked list
     head = Reverse(head);
     cout <<"\nReversed list: " ;
     printList(head);
     return 0;
}

Java

//Java implementation to reverse a doubly 
//linked list using recursion 
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 
//of the Doubly Linked List 
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 
     new_node.next = (head_ref); 
  
     //change prev of head node to new node 
     if ((head_ref) != null ) 
         (head_ref).prev = new_node; 
  
     //move the head to point to the new node 
     (head_ref) = new_node; 
     return head_ref;
} 
  
//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 
//linked list 
static void printList(Node head) 
{ 
     while (head != null )
     { 
         System.out.print( head.data + " " ); 
         head = head.next; 
     } 
} 
  
//Driver code 
public static void main(String args[]) 
{ 
     //Start with the empty list 
     Node head = null ; 
  
     //Create doubly linked: 10<.8<.4<.2 /
     head = push(head, getNode( 2 )); 
     head = push(head, getNode( 4 )); 
     head = push(head, getNode( 8 )); 
     head = push(head, getNode( 10 )); 
     System.out.print( "Original list: " ); 
     printList(head); 
  
     //Reverse doubly linked list 
     head = Reverse(head); 
     System.out.print( "\nReversed list: " ); 
     printList(head); 
} 
}
  
//This code is contributed by Arnab Kundu

Python3

# Python3 implementation to reverse a doubly
# linked list using recursion
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
def push(head_ref, new_node):
      
     # since we are adding at the beginning, # prev is always None
     new_node.prev = None
  
     # link the old list off the new node
     new_node. next = head_ref
  
     # change prev of head node to new node
     if (head_ref ! = None ):
         head_ref.prev = new_node
  
     # move the head to point to the new node
     head_ref = new_node
     return head_ref
  
# 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
# linked list
def printList(head):
     while (head ! = None ) :
         print (head.data, end = " " )
         head = head. next
      
# Driver Code
if __name__ = = '__main__' : 
      
     # Start with the empty list
     head = None
  
     # Create doubly linked: 10<.8<.4<.2 */
     head = push(head, getNode( 2 )); 
     head = push(head, getNode( 4 )); 
     head = push(head, getNode( 8 )); 
     head = push(head, getNode( 10 ));
     print ( "Original list: " , end = "")
     printList(head)
      
     # Reverse doubly linked list
     head = Reverse(head)
     print ( "\nReversed list: " , end = "")
     printList(head)
      
# This code is contributed by Srathore

C#

//C# implementation to reverse a doubly 
using System;
  
//linked list using recursion 
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 
//of the Doubly Linked List 
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 
     new_node.next = (head_ref); 
  
     //change prev of head node to new node 
     if ((head_ref) != null ) 
         (head_ref).prev = new_node; 
  
     //move the head to point to the new node 
     (head_ref) = new_node; 
     return head_ref; 
} 
  
//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 
//linked list 
static void printList(Node head) 
{ 
     while (head != null ) 
     { 
         Console.Write( head.data + " " ); 
         head = head.next; 
     } 
} 
  
//Driver code 
public static void Main(String []argsS) 
{ 
     //Start with the empty list 
     Node head = null ; 
  
     //Create doubly linked: 10<.8<.4<.2 /
     head = push(head, getNode(2)); 
     head = push(head, getNode(4)); 
     head = push(head, getNode(8)); 
     head = push(head, getNode(10)); 
     Console.Write( "Original list: " ); 
     printList(head); 
  
     //Reverse doubly linked list 
     head = Reverse(head); 
     Console.Write( "\nReversed list: " ); 
     printList(head); 
} 
} 
  
//This code is contributed by Arnab Kundu

输出如下：

Original list: 10 8 4 2   
Reversed list: 2 4 8 10

---