# 带头和尾指针的双链表中的排序插入

2021年5月13日16:50:13 发表评论 1,122 次浏览

## 本文概述

``````Input : 40 50 10 45 90 100 95
Output :10 40 45 50 90 95 100

Input : 30 10 50 43 56 12
Output :10 12 30 43 50 56``````

1. 如果"链接列表"为空, 则使左指针和右指针都指向要插入的节点, 并使它的上一个和下一个字段指向NULL。
2. 如果要插入的节点的值小于链接列表的第一个节点的值, 则从第一个节点的前一个字段连接该节点。
3. 如果要插入的节点的值大于链接列表的最后一个节点的值, 则从最后一个节点的下一个字段连接该节点。
4. 如果要插入的节点的值在第一个节点与最后一个节点的值之间, 则检查适当的位置并建立连接。

## 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;

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
{
(*tail) = p;
return ;
}

//If node to be insetailed has value less
//than first node
{
p->prev = NULL;
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.
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);

" from left to right\n" ;
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>

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
{
(*tail) = p;
return ;
}

//If node to be insetailed has value less
//than first node
{
p->prev = NULL;
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.
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 ( "\nDoubly linked list on printing"
" from left to right\n" );
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.*;

class Node
{
int info;
Node prev, next;
}

class GFG
{

//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
{
tail = p;
return ;
}

//If node to be insetailed has value less
//than first node
{
p.prev = null ;
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.
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" );
}
}

//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

class Node:
def __init__( self , data):
self .info = data
self . next = None
self .prev = None

tail = None

# Function to insetail new node
def nodeInsetail( key) :

global tail

p = Node( 0 )
p.info = key
p. next = None

# If first node to be insetailed in doubly
if ((head) = = None ) :
(tail) = p
return

# If node to be insetailed has value less
# than first node
p.prev = None
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.
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\n" )

# 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;

public class Node
{
public int info;
public Node prev, next;
}

class GFG
{

//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
{
tail = p;
return ;
}

//If node to be insetailed has value less
//than first node
{
p.prev = null ;
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.
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" );
``````Doubly linked list on printing from left to right