A. 双链表 是一个链表，由一组称为节点的顺序链接记录组成。每个节点包含两个字段，分别引用节点序列中的上一个节点和下一个节点。 任务是通过插入节点创建一个双链接列表，这样列表在从左到右打印时保持升序。此外，我们需要维护两个指针，head（指向第一个节点）和tail（指向最后一个节点）。 例如：
null
Input : 40 50 10 45 90 100 95Output :10 40 45 50 90 95 100Input : 30 10 50 43 56 12Output :10 12 30 43 50 56
算法： 这项任务可以通过以下方式完成：
- 如果链表为空，则使左右指针都指向要插入的节点，并使其上一个和下一个字段都指向NULL。
- 如果要插入的节点的值小于链表第一个节点的值，则从第一个节点的上一个字段连接该节点。
- 如果要插入的节点的值大于链表最后一个节点的值，则从最后一个节点的下一个字段连接该节点。
- 如果要插入的节点的值介于第一个和最后一个节点的值之间，则检查适当的位置并进行连接。
C++
/* C++ program to insetail nodes in doubly linked list such that list remains in ascending order on printing from left to right */ #include <bits/stdc++.h> using namespace std; // A linked list node class Node { public : Node *prev; int info; Node *next; }; // Function to insetail new node void nodeInsetail(Node **head, Node **tail, int key) { Node *p = new Node(); p->info = key; p->next = NULL; // If first node to be insetailed in doubly // linked list if ((*head) == NULL) { (*head) = p; (*tail) = p; (*head)->prev = NULL; return ; } // If node to be insetailed has value less // than first node if ((p->info) < ((*head)->info)) { p->prev = NULL; (*head)->prev = p; p->next = (*head); (*head) = p; return ; } // If node to be insetailed has value more // than last node if ((p->info) > ((*tail)->info)) { p->prev = (*tail); (*tail)->next = p; (*tail) = p; return ; } // Find the node before which we need to // insert p. Node *temp = (*head)->next; while ((temp->info) < (p->info)) temp = temp->next; // Insert new node before temp (temp->prev)->next = p; p->prev = temp->prev; temp->prev = p; p->next = temp; } // Function to print nodes in from left to right void printList(Node *temp) { while (temp != NULL) { cout << temp->info << " " ; temp = temp->next; } } // Driver program to test above functions int main() { Node *left = NULL, *right = NULL; nodeInsetail(&left, &right, 30); nodeInsetail(&left, &right, 50); nodeInsetail(&left, &right, 90); nodeInsetail(&left, &right, 10); nodeInsetail(&left, &right, 40); nodeInsetail(&left, &right, 110); nodeInsetail(&left, &right, 60); nodeInsetail(&left, &right, 95); nodeInsetail(&left, &right, 23); cout<< "Doubly linked list on printing" " from left to right" ; printList(left); return 0; } // This is code is contributed by rathbhupendra |
C
/* C program to insetail nodes in doubly linked list such that list remains in ascending order on printing from left to right */ #include<stdio.h> #include<stdlib.h> // A linked list node struct Node { struct Node *prev; int info; struct Node *next; }; // Function to insetail new node void nodeInsetail( struct Node **head, struct Node **tail, int key) { struct Node *p = new Node; p->info = key; p->next = NULL; // If first node to be insetailed in doubly // linked list if ((*head) == NULL) { (*head) = p; (*tail) = p; (*head)->prev = NULL; return ; } // If node to be insetailed has value less // than first node if ((p->info) < ((*head)->info)) { p->prev = NULL; (*head)->prev = p; p->next = (*head); (*head) = p; return ; } // If node to be insetailed has value more // than last node if ((p->info) > ((*tail)->info)) { p->prev = (*tail); (*tail)->next = p; (*tail) = p; return ; } // Find the node before which we need to // insert p. temp = (*head)->next; while ((temp->info) < (p->info)) temp = temp->next; // Insert new node before temp (temp->prev)->next = p; p->prev = temp->prev; temp->prev = p; p->next = temp; } // Function to print nodes in from left to right void printList( struct Node *temp) { while (temp != NULL) { printf ( "%d " , temp->info); temp = temp->next; } } // Driver program to test above functions int main() { struct Node *left = NULL, *right = NULL; nodeInsetail(&left, &right, 30); nodeInsetail(&left, &right, 50); nodeInsetail(&left, &right, 90); nodeInsetail(&left, &right, 10); nodeInsetail(&left, &right, 40); nodeInsetail(&left, &right, 110); nodeInsetail(&left, &right, 60); nodeInsetail(&left, &right, 95); nodeInsetail(&left, &right, 23); printf ( "Doubly linked list on printing" " from left to right" ); printList(left); return 0; } |
JAVA
/* Java program to insetail nodes in doubly linked list such that list remains in ascending order on printing from left to right */ import java.io.*; import java.util.*; // A linked list node class Node { int info; Node prev, next; } class GFG { static Node head, tail; // Function to insetail new node static void nodeInsetail( int key) { Node p = new Node(); p.info = key; p.next = null ; // If first node to be insetailed in doubly // linked list if (head == null ) { head = p; tail = p; head.prev = null ; return ; } // If node to be insetailed has value less // than first node if (p.info < head.info) { p.prev = null ; head.prev = p; p.next = head; head = p; return ; } // If node to be insetailed has value more // than last node if (p.info > tail.info) { p.prev = tail; tail.next = p; tail = p; return ; } // Find the node before which we need to // insert p. Node temp = head.next; while (temp.info < p.info) temp = temp.next; // Insert new node before temp (temp.prev).next = p; p.prev = temp.prev; temp.prev = p; p.next = temp; } // Function to print nodes in from left to right static void printList(Node temp) { while (temp != null ) { System.out.print(temp.info + " " ); temp = temp.next; } } // Driver code public static void main(String args[]) { head = tail = null ; nodeInsetail( 30 ); nodeInsetail( 50 ); nodeInsetail( 90 ); nodeInsetail( 10 ); nodeInsetail( 40 ); nodeInsetail( 110 ); nodeInsetail( 60 ); nodeInsetail( 95 ); nodeInsetail( 23 ); System.out.println( "Doubly linked list on printing from left to right" ); printList(head); } } // This code is contributed by rachana soma |
python
# Python program to insetail nodes in doubly # linked list such that list remains in # ascending order on printing from left # to right # Linked List node class Node: def __init__( self , data): self .info = data self . next = None self .prev = None head = None tail = None # Function to insetail new node def nodeInsetail( key) : global head global tail p = Node( 0 ) p.info = key p. next = None # If first node to be insetailed in doubly # linked list if ((head) = = None ) : (head) = p (tail) = p (head).prev = None return # If node to be insetailed has value less # than first node if ((p.info) < ((head).info)) : p.prev = None (head).prev = p p. next = (head) (head) = p return # If node to be insetailed has value more # than last node if ((p.info) > ((tail).info)) : p.prev = (tail) (tail). next = p (tail) = p return # Find the node before which we need to # insert p. temp = (head). next while ((temp.info) < (p.info)) : temp = temp. next # Insert new node before temp (temp.prev). next = p p.prev = temp.prev temp.prev = p p. next = temp # Function to print nodes in from left to right def printList(temp) : while (temp ! = None ) : print ( temp.info, end = " " ) temp = temp. next # Driver program to test above functions nodeInsetail( 30 ) nodeInsetail( 50 ) nodeInsetail( 90 ) nodeInsetail( 10 ) nodeInsetail( 40 ) nodeInsetail( 110 ) nodeInsetail( 60 ) nodeInsetail( 95 ) nodeInsetail( 23 ) print ( "Doubly linked list on printing from left to right" ) printList(head) # This code is contributed by Arnab Kundu |
C#
/* C# program to insetail nodes in doubly linked list such that list remains in ascending order on printing from left to right */ using System; // A linked list node public class Node { public int info; public Node prev, next; } class GFG { static Node head, tail; // Function to insetail new node static void nodeInsetail( int key) { Node p = new Node(); p.info = key; p.next = null ; // If first node to be insetailed in doubly // linked list if (head == null ) { head = p; tail = p; head.prev = null ; return ; } // If node to be insetailed has value less // than first node if (p.info < head.info) { p.prev = null ; head.prev = p; p.next = head; head = p; return ; } // If node to be insetailed has value more // than last node if (p.info > tail.info) { p.prev = tail; tail.next = p; tail = p; return ; } // Find the node before which we need to // insert p. Node temp = head.next; while (temp.info < p.info) temp = temp.next; // Insert new node before temp (temp.prev).next = p; p.prev = temp.prev; temp.prev = p; p.next = temp; } // Function to print nodes in from left to right static void printList(Node temp) { while (temp != null ) { Console.Write(temp.info + " " ); temp = temp.next; } } // Driver code public static void Main(String []args) { head = tail = null ; nodeInsetail(30); nodeInsetail(50); nodeInsetail(90); nodeInsetail(10); nodeInsetail(40); nodeInsetail(110); nodeInsetail(60); nodeInsetail(95); nodeInsetail(23); Console.WriteLine( "Doubly linked list on printing from left to right" ); printList(head); } } // This code is contributed by Arnab Kundu |
Javascript
<script> /* javascript program to insetail nodes in doubly linked list such that list remains in ascending order on printing from left to right */ // A linked list node class Node { constructor() { this .info = 0; this .prev = null ; this .next = null ; } } var head, tail; // Function to insetail new node function nodeInsetail(key) { p = new Node(); p.info = key; p.next = null ; // If first node to be insetailed in doubly // linked list if (head == null ) { head = p; tail = p; head.prev = null ; return ; } // If node to be insetailed has value less // than first node if (p.info < head.info) { p.prev = null ; head.prev = p; p.next = head; head = p; return ; } // If node to be insetailed has value more // than last node if (p.info > tail.info) { p.prev = tail; tail.next = p; tail = p; return ; } // Find the node before which we need to // insert p. temp = head.next; while (temp.info < p.info) temp = temp.next; // Insert new node before temp (temp.prev).next = p; p.prev = temp.prev; temp.prev = p; p.next = temp; } // Function to print nodes in from left to right function printList( temp) { while (temp != null ) { document.write(temp.info + " " ); temp = temp.next; } } // Driver code head = tail = null ; nodeInsetail(30); nodeInsetail(50); nodeInsetail(90); nodeInsetail(10); nodeInsetail(40); nodeInsetail(110); nodeInsetail(60); nodeInsetail(95); nodeInsetail(23); document.write( "Doubly linked list on printing from left to right<br/>" ); printList(head); // This code is contributed by aashish1995 </script> |
输出：
Doubly linked list on printing from left to right10 23 30 40 50 60 90 95 110
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
