在排序的双向链表中插入一个节点

Question

在双向排序的链表中插入节点每次插入后，链表都应该排序

节点定义为

struct Node
   {
     int data;
     Node *next;
     Node *prev;
   }

下面写了一个函数逻辑..

Node* SortedInsert(Node *head,int data)
{
    // Complete this function
   // Do not write the main method. 
    struct Node *newn= (struct Node*)malloc(sizeof(struct Node*));
    newn->data= data;
    newn->next= newn->prev= NULL;

    struct Node *trav=head, *pre=NULL;

    if(head==NULL)
        head= newn;
    else if(newn->data <= trav->data)
    {
        newn->next= trav;
        trav->prev= newn;
        head= newn;
    }
    else
    {
        while(trav->data <= newn->data)
        {
            pre= trav;
            trav=trav->next; 
        }
        pre= trav;
        trav=trav->next;

        newn->next= trav;
        trav->prev= newn;
        pre->next= newn;
        newn->prev= pre;
    }
    return head;
}

请让我知道逻辑有什么问题

Answer 1

你犯了一个小错误，首先space是这样分配的：

struct Node *newn= (struct Node*)malloc(sizeof(struct Node));

正确的else条件是：

else
{           
 while(trav!=NULL&&trav->data <= newn->data)
 {
  pre= trav;
  trav=trav->next; 
 }
 newn->prev=pre;
 newn->next=trav;
 pre->next=newn;
 if(trav!=NULL)
  trav->prev=newn;
}

在排序的双向链表中插入一个节点

inserting a node in sorted doubly linked list

data-structures

insert

linked-list

doubly-linked-list

sortedlist