对给定的生物音素双链表进行排序。生物音素双链表是一个先增加后减少的双链表。严格递增或严格递减链表也是生物音素双链表。 例如：
null
![图片[1]-对生物音素双链表排序-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_dll14.jpg)
方法： 查找列表中比上一个节点小的第一个节点。顺其自然 现在的 。如果不存在此类节点，则列表已排序。否则将列表拆分为两个列表， 第一 从 头 直到 当前的 上一个节点和 第二 从 现在的 节点，直到列表的末尾。颠倒方向 第二 双链表。参考 这 邮递现在合并 第一 和 第二 排序的双链表。请参阅合并程序 这 邮递最终的合并列表是所需的排序双链接列表。
C++
// C++ implementation to sort the biotonic doubly linked list #include <bits/stdc++.h> using namespace std; // a node of the doubly linked list struct Node { int data; struct Node* next; struct Node* prev; }; // Function to reverse a Doubly Linked List void reverse( struct Node** head_ref) { struct Node* temp = NULL; struct Node* current = *head_ref; // swap next and prev for all nodes // of doubly linked list while (current != NULL) { temp = current->prev; current->prev = current->next; current->next = temp; current = current->prev; } // Before changing head, check for the cases // like empty list and list with only one node if (temp != NULL) *head_ref = temp->prev; } // Function to merge two sorted doubly linked lists struct Node* merge( struct Node* first, struct Node* second) { // If first linked list is empty if (!first) return second; // If second linked list is empty if (!second) return first; // Pick the smaller value if (first->data < second->data) { first->next = merge(first->next, second); first->next->prev = first; first->prev = NULL; return first; } else { second->next = merge(first, second->next); second->next->prev = second; second->prev = NULL; return second; } } // function to sort a biotonic doubly linked list struct Node* sort( struct Node* head) { // if list is empty or if it contains a single // node only if (head == NULL || head->next == NULL) return head; struct Node* current = head->next; while (current != NULL) { // if true, then 'current' is the first node // which is smaller than its previous node if (current->data < current->prev->data) break ; // move to the next node current = current->next; } // if true, then list is already sorted if (current == NULL) return head; // split into two lists, one starting with 'head' // and other starting with 'current' current->prev->next = NULL; current->prev = NULL; // reverse the list starting with 'current' reverse(¤t); // merge the two lists and return the // final merged doubly linked list return merge(head, current); } // Function to insert a node at the beginning // of the Doubly Linked List void push( struct Node** head_ref, int new_data) { // allocate node struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); // put in the data new_node->data = new_data; // 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 print nodes in a given doubly // linked list void printList( struct Node* head) { // if list is empty if (head == NULL) cout << "Doubly Linked list empty" ; while (head != NULL) { cout << head->data << " " ; head = head->next; } } // Driver program to test above int main() { struct Node* head = NULL; // Create the doubly linked list: // 2<->5<->7<->12<->10<->6<->4<->1 push(&head, 1); push(&head, 4); push(&head, 6); push(&head, 10); push(&head, 12); push(&head, 7); push(&head, 5); push(&head, 2); cout << "Original Doubly linked list:n" ; printList(head); // sort the biotonic DLL head = sort(head); cout << "Doubly linked list after sorting:n" ; printList(head); return 0; } |
JAVA
// Java implementation to sort the // biotonic doubly linked list class GFG { // a node of the doubly linked list static class Node { int data; Node next; Node prev; } // Function to reverse a Doubly Linked List static Node reverse( Node head_ref) { Node temp = null ; Node current = head_ref; // swap next and prev for all nodes // of doubly linked list while (current != null ) { temp = current.prev; current.prev = current.next; current.next = temp; current = current.prev; } // Before changing head, check for the cases // like empty list and list with only one node if (temp != null ) head_ref = temp.prev; return head_ref; } // Function to merge two sorted doubly linked lists static Node merge(Node first, Node second) { // If first linked list is empty if (first == null ) return second; // If second linked list is empty if (second == null ) return first; // Pick the smaller value if (first.data < second.data) { first.next = merge(first.next, second); first.next.prev = first; first.prev = null ; return first; } else { second.next = merge(first, second.next); second.next.prev = second; second.prev = null ; return second; } } // function to sort a biotonic doubly linked list static Node sort(Node head) { // if list is empty or if it contains // a single node only if (head == null || head.next == null ) return head; Node current = head.next; while (current != null ) { // if true, then 'current' is the first node // which is smaller than its previous node if (current.data < current.prev.data) break ; // move to the next node current = current.next; } // if true, then list is already sorted if (current == null ) return head; // split into two lists, one starting with 'head' // and other starting with 'current' current.prev.next = null ; current.prev = null ; // reverse the list starting with 'current' current = reverse(current); // merge the two lists and return the // final merged doubly linked list return merge(head, current); } // Function to insert a node at the beginning // of the Doubly Linked List static Node push( Node head_ref, int new_data) { // allocate node Node new_node = new Node(); // put in the data new_node.data = new_data; // 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 print nodes in a given doubly // linked list static void printList( Node head) { // if list is empty if (head == null ) System.out.println( "Doubly Linked list empty" ); while (head != null ) { System.out.print(head.data + " " ); head = head.next; } } // Driver Code public static void main(String args[]) { Node head = null ; // Create the doubly linked list: // 2<.5<.7<.12<.10<.6<.4<.1 head = push(head, 1 ); head = push(head, 4 ); head = push(head, 6 ); head = push(head, 10 ); head = push(head, 12 ); head = push(head, 7 ); head = push(head, 5 ); head = push(head, 2 ); System.out.println( "Original Doubly linked list:n" ); printList(head); // sort the biotonic DLL head = sort(head); System.out.println( "Doubly linked list after sorting:n" ); printList(head); } } // This code is contributed by Arnab Kundu |
python
# Python implementation to sort the # biotonic doubly linked list # Node of a doubly linked list class Node: def __init__( self , next = None , prev = None , data = None ): self . next = next self .prev = prev self .data = data # Function to reverse a Doubly Linked List def reverse( head_ref): temp = None current = head_ref # swap next and prev for all nodes # of doubly linked list while (current ! = None ): temp = current.prev current.prev = current. next current. next = temp current = current.prev # Before changing head, check for the cases # like empty list and list with only one node if (temp ! = None ): head_ref = temp.prev return head_ref # Function to merge two sorted doubly linked lists def merge( first, second): # If first linked list is empty if (first = = None ): return second # If second linked list is empty if (second = = None ): return first # Pick the smaller value if (first.data < second.data): first. next = merge(first. next , second) first. next .prev = first first.prev = None return first else : second. next = merge(first, second. next ) second. next .prev = second second.prev = None return second # function to sort a biotonic doubly linked list def sort( head): # if list is empty or if it contains # a single node only if (head = = None or head. next = = None ): return head current = head. next while (current ! = None ) : # if true, then 'current' is the first node # which is smaller than its previous node if (current.data < current.prev.data): break # move to the next node current = current. next # if true, then list is already sorted if (current = = None ): return head # split into two lists, one starting with 'head' # and other starting with 'current' current.prev. next = None current.prev = None # reverse the list starting with 'current' current = reverse(current) # merge the two lists and return the # final merged doubly linked list return merge(head, current) # Function to insert a node at the beginning # of the Doubly Linked List def push( head_ref, new_data): # allocate node new_node = Node() # put in the data new_node.data = new_data # 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 print nodes in a given doubly # linked list def printList( head): # if list is empty if (head = = None ): print ( "Doubly Linked list empty" ) while (head ! = None ): print (head.data, end = " " ) head = head. next # Driver Code head = None # Create the doubly linked list: # 2<.5<.7<.12<.10<.6<.4<.1 head = push(head, 1 ) head = push(head, 4 ) head = push(head, 6 ) head = push(head, 10 ) head = push(head, 12 ) head = push(head, 7 ) head = push(head, 5 ) head = push(head, 2 ) print ( "Original Doubly linked list:n" ) printList(head) # sort the biotonic DLL head = sort(head) print ( "Doubly linked list after sorting:" ) printList(head) # This code is contributed by Arnab Kundu |
C#
// C# implementation to sort the // biotonic doubly linked list using System; class GFG { // a node of the doubly linked list public class Node { public int data; public Node next; public Node prev; } // Function to reverse a Doubly Linked List static Node reverse( Node head_ref) { Node temp = null ; Node current = head_ref; // swap next and prev for all nodes // of doubly linked list while (current != null ) { temp = current.prev; current.prev = current.next; current.next = temp; current = current.prev; } // Before changing head, check for the cases // like empty list and list with only one node if (temp != null ) head_ref = temp.prev; return head_ref; } // Function to merge two sorted doubly linked lists static Node merge(Node first, Node second) { // If first linked list is empty if (first == null ) return second; // If second linked list is empty if (second == null ) return first; // Pick the smaller value if (first.data < second.data) { first.next = merge(first.next, second); first.next.prev = first; first.prev = null ; return first; } else { second.next = merge(first, second.next); second.next.prev = second; second.prev = null ; return second; } } // function to sort a biotonic doubly linked list static Node sort(Node head) { // if list is empty or if it contains // a single node only if (head == null || head.next == null ) return head; Node current = head.next; while (current != null ) { // if true, then 'current' is the first node // which is smaller than its previous node if (current.data < current.prev.data) break ; // move to the next node current = current.next; } // if true, then list is already sorted if (current == null ) return head; // split into two lists, one starting with 'head' // and other starting with 'current' current.prev.next = null ; current.prev = null ; // reverse the list starting with 'current' current = reverse(current); // merge the two lists and return the // final merged doubly linked list return merge(head, current); } // Function to insert a node at the beginning // of the Doubly Linked List static Node push( Node head_ref, int new_data) { // allocate node Node new_node = new Node(); // put in the data new_node.data = new_data; // 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 print nodes in a given doubly // linked list static void printList( Node head) { // if list is empty if (head == null ) Console.WriteLine( "Doubly Linked list empty" ); while (head != null ) { Console.Write(head.data + " " ); head = head.next; } } // Driver Code public static void Main(String []args) { Node head = null ; // Create the doubly linked list: // 2<.5<.7<.12<.10<.6<.4<.1 head = push(head, 1); head = push(head, 4); head = push(head, 6); head = push(head, 10); head = push(head, 12); head = push(head, 7); head = push(head, 5); head = push(head, 2); Console.WriteLine( "Original Doubly linked list:n" ); printList(head); // sort the biotonic DLL head = sort(head); Console.WriteLine( "Doubly linked list after sorting:n" ); printList(head); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // javascript implementation to sort the // biotonic doubly linked list // a node of the doubly linked list class Node { constructor() { this .data = 0; this .prev = null ; this .next = null ; } } // Function to reverse a Doubly Linked List function reverse(head_ref) { var temp = null ; var current = head_ref; // swap next and prev for all nodes // of doubly linked list while (current != null ) { temp = current.prev; current.prev = current.next; current.next = temp; current = current.prev; } // Before changing head, check for the cases // like empty list and list with only one node if (temp != null ) head_ref = temp.prev; return head_ref; } // Function to merge two sorted doubly linked lists function merge(first, second) { // If first linked list is empty if (first == null ) return second; // If second linked list is empty if (second == null ) return first; // Pick the smaller value if (first.data < second.data) { first.next = merge(first.next, second); first.next.prev = first; first.prev = null ; return first; } else { second.next = merge(first, second.next); second.next.prev = second; second.prev = null ; return second; } } // function to sort a biotonic doubly linked list function sort(head) { // if list is empty or if it contains // a single node only if (head == null || head.next == null ) return head; var current = head.next; while (current != null ) { // if true, then 'current' is the first node // which is smaller than its previous node if (current.data < current.prev.data) break ; // move to the next node current = current.next; } // if true, then list is already sorted if (current == null ) return head; // split into two lists, one starting with 'head' // and other starting with 'current' current.prev.next = null ; current.prev = null ; // reverse the list starting with 'current' current = reverse(current); // merge the two lists and return the // final merged doubly linked list return merge(head, current); } // Function to insert a node at the beginning // of the Doubly Linked List function push(head_ref , new_data) { // allocate node var new_node = new Node(); // put in the data new_node.data = new_data; // 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 print nodes in a given doubly // linked list function printList(head) { // if list is empty if (head == null ) document.write( "Doubly Linked list empty" ); while (head != null ) { document.write(head.data + " " ); head = head.next; } } // Driver Code var head = null ; // Create the doubly linked list: // 2<.5<.7<.12<.10<.6<.4<.1 head = push(head, 1); head = push(head, 4); head = push(head, 6); head = push(head, 10); head = push(head, 12); head = push(head, 7); head = push(head, 5); head = push(head, 2); document.write( "Original Doubly linked list:<br/>" ); printList(head); // sort the biotonic DLL head = sort(head); document.write( "<br/>Doubly linked list after sorting:<br/>" ); printList(head); // This code contributed by aashish1995 </script> |
输出：
Original Doubly linked list:2 5 7 12 10 6 4 1Doubly linked list after sorting:1 2 4 5 6 7 10 12
时间复杂度：O（n） 本文由 阿尤什·焦哈里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
