给出了一个双链接列表。使用递归将其反转。
null
Original Doubly linked list
![图片[1]-使用递归反转双链表-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_1-25.jpg)
Reversed Doubly linked list
![图片[2]-使用递归反转双链表-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_2-23.jpg)
我们讨论过 双链表逆问题的迭代解法 算法 1） 如果列表为空，则返回 2） 通过交换head->prev和head->next来反转head 3） 如果prev=NULL，则表示列表完全颠倒。否则反转（头部->上一个）
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 << "Reversed 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( "Reversed 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 ( "Reversed 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( "Reversed list: " ); printList(head); } } // This code is contributed by Arnab Kundu |
Javascript
<script> // javascript implementation to reverse a doubly // linked list using recursion // a node of the doubly linked list class Node { constructor(val) { this .data = val; this .prev = null ; this .next = null ; } } // function to get a new node function getNode(data) { // allocate space var 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 function push(head_ref, 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 function Reverse(node) { // If empty list, return if (node == null ) return null ; // Otherwise, swap the next and prev var 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 function printList(head) { while (head != null ) { document.write(head.data + " " ); head = head.next; } } // Driver code // Start with the empty list var 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)); document.write( "Original list: " ); printList(head); // Reverse doubly linked list head = Reverse(head); document.write( "<br/>Reversed list: " ); printList(head); // This code contributed by umadevi9616 </script> |
输出：
Original list: 10 8 4 2 Reversed list: 2 4 8 10
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
