在已排序的双向链接列表中插入节点

I am not able to figure out, why is my code to insert into a sorted doubly linked list failing on some test cases.Please let me know. I dont know of the test cases, they are system generated.

我无法弄清楚,为什么我的代码插入到排序的双链表中,在某些测试用例中失败。请让我知道。我不知道测试用例,它们是系统生成的。

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

    if (temp->data <= head->data)
    {
        temp->next = head;
        head->prev = temp;
        head = temp;
        return head;
    }

    Node *curr = head;
    while (curr->next!=NULL)
    {
        if (temp->data <= curr->data)
        {   
            curr->prev->next = temp;
            temp->prev = curr->prev;
            temp->next = curr;
            curr->prev = temp;
            return head;
        }

        curr = curr->next;
    }

    curr->next = temp;
    temp->prev = curr;
    return head;
}

Thanks

5 个解决方案

#1

Once you reach the last node, you should again compare its data with the new node and insert accordingly.

到达最后一个节点后,您应该再次将其数据与新节点进行比较并相应地插入。

    curr->next = temp;
    temp->prev = curr;
    return head;
}

If execution reaches this part, then at present curr is pointing to the last node. Now you should again compare its data like the following:

如果执行到达此部分,则当前curr指向最后一个节点。现在你应该再次比较它的数据,如下所示:

    if (temp->data <= curr->data)
    {   // insert before last node
        curr->prev->next = temp;
        temp->prev = curr->prev;
        temp->next = curr;
        curr->prev = temp;
        return head;
    }
    // else insert at the end.
    curr->next = temp;
    temp->prev = curr;
    return head;
}

#2

Alternatively, you can write an if condition for node at the end of the list

或者,您可以在列表末尾为节点编写if条件

Node* SortedInsert(Node *head,int data)
{
struct Node* p = head;
struct Node* q = NULL;
    struct Node* r = new Node;
    r->data=data;
    r->prev=NULL;
    r->next=NULL;

    if(p==NULL){
        p=r;
        head=p;
    }
    else if(p!=NULL&&p->data>r->data){
        p->prev=r;
        r->next=p;
        p->next=NULL;
        head = r;
    }
    else{
                p=head;
        while(p!=NULL) {

              if(p!=NULL&&p->data>r->data){   //If node is not at the end of list and smaller than some node

                  (p->prev)->next = r;
                  r->next = p;
                  r->prev = p->prev;
                  p->prev=r;
             return head;
        }
        else if(p->next==NULL)           //If node is at the end of list
            {

            p->next = r;
            r->prev = p;
           r->next = NULL;
            return head;
        }
            else{}
     p=p->next; 
          }
    }
 return head;

}

#3

Here is some code in order to Insert a Node in Sorted Doubly Linked List

下面是一些代码,以便在排序的双向链接列表中插入节点

Node* SortedInsert(Node *head,int data)
 {
  struct Node *temp;
  struct Node *newNode = new Node();
  newNode->data=data;
  newNode->next=NULL;
  newNode->prev=NULL;
  temp=head;

if(head==NULL)
 {
    head = newNode;      
 }

else
 {
    while(temp!=NULL)
    {
        if(temp->data<data&&temp->next!=NULL)
        {
            temp=temp->next;
        }
        else
            {
            if(temp->next==NULL&&temp->data<data)
                {
                temp->next = newNode;
                newNode->prev = temp;
                break;
            }

           else if(temp->prev==NULL&&temp->data>data)
                {
                newNode->next=temp;
                temp->prev = newNode;
                head=newNode;
                break;
            }

           else
                {
                newNode->next = temp;
                newNode->prev = temp->prev;
                temp->prev->next =newNode;
                temp->prev=newNode;
                break;
                }    
             }
         }
   }
  return head;
}

#4

Here is the complete C++ program for inserting a node at appropriate position in a sorted doubly linked list:

这是一个完整的C ++程序,用于在排序的双向链表中的适当位置插入节点:

void InsertInSortedDoublyLinkedList()
    {
        Node *head;
        head = CreateDoublyLinkList(3);
        PrintDoublyLinkedList(head);
        head = SortedInsert(head, 6);
        printf("\n Linked list after insertion in sorted order\n");
        PrintDoublyLinkedList(head);
    }

void PrintDoublyLinkedList(Node *head)
{
    Node *temp = head;
    printf("NULL -> ");
    while (temp)
    {
        printf("%d ->", temp->data);
        temp = temp->next;
    }
    printf("NULL");
}


Node* CreateDoublyLinkList(int numberOfNodes)
{
    Node *head = NULL, *temp, *temp1;
    int startingValue = 3;

    if (numberOfNodes == 0)
    {
        return head;
    }

    temp = (Node*)malloc(sizeof(Node));
    temp->data = startingValue;
    temp->next = NULL;
    temp->prev = NULL;
    head = temp;
    startingValue += 2;
    numberOfNodes--;
    for (; numberOfNodes > 0; numberOfNodes--, startingValue += 2, temp = temp->next)
    {
        temp1 = (Node*)malloc(sizeof(Node));
        temp1->data = startingValue;
        temp1->next = NULL;
        temp1->prev = temp;
        temp->next = temp1;
    }

    return head;
}

Node* SortedInsert(Node *head,int data)
{
        Node *temp = NULL, *temp1,*newNode;
        int nodeInserted = 0;
        if (head == NULL)
        {
            head = (Node*) malloc(sizeof(Node));
            head->data = data;
            head->next = NULL;
            head->prev = NULL;
        }
        else
        {
            if (head->data > data)
            {
                //insertion need to take place before head itself.
                newNode = (Node*)malloc(sizeof(Node));
                newNode->data = data;
                newNode->next = head;
                newNode->prev = NULL;
                head->prev = newNode;
                head = newNode;
            }
            else
            {
                temp1 = head;
                temp = head ->next;
                while (temp)
                {
                    if (temp->data > data)
                    {
                        //we need to insert the node before temp
                        newNode = (Node*)malloc(sizeof(Node));
                        newNode->data = data;
                        newNode->prev = temp1;
                        newNode->next = temp;


                        temp1->next = newNode;
                        temp->prev = newNode;
                        nodeInserted = 1;
                        break;
                    }
                    temp1 = temp;
                    temp = temp->next;
                }
                if (!nodeInserted)
                {
                    //node insertion need to take place at tail.
                    newNode = (Node*)malloc(sizeof(Node));
                    newNode->data = data;
                    newNode->prev = temp1;
                    newNode->next = NULL;
                    temp1->next = newNode;
                }

            }

        }

        return head;
}

#5

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

            Node* SortedInsert(Node *head,int data)
            {
                Node* p1,*p2;
                int n=10;
                p2=(Node*)malloc(sizeof(struct Node));
                p2->next=NULL;
                p2->prev=NULL;
                p2->data=data;

                p1=head;
                if(p1==NULL)
                    return p2;

                while(p1->next!=NULL)
                    {
                    if(p1->data<data)
                        p1=p1->next;
                    else 
                        break;
                    }
                /*Three cases arise when p1->next == NUll i.e. we are end of list
                case 1: insert after the end
                case 2: insert in between last and second last node
                case 3: insert node at the beginning of the list
                */
                if(p1->next==NULL)
                    {
                        if(p1->data<data)
                            {
                                p2->prev=p1;
                                p1->next=p2;
                            }
                        else if(p1->data > data && p1->prev!=NULL)
                            {
                            p2->next=p1;
                            p2->prev=p1->prev;
                            if(p1->prev!=NULL)
                            p1->prev->next=p2;
                            p1->prev=p2;
                        }
                        else
                            {
                                p2->next=p1;
                                p2->prev=p1->prev;
                                if(p1->prev!=NULL)
                                p1->prev->next=p2;
                                p1->prev=p2;
                                head=p2;
                            }
                    }

                // Here we have only one case where new node is inserted between two nodes of the list
                else
                    {
                        p2->next=p1;
                        p2->prev=p1->prev;
                        if(p1->prev!=NULL)
                        p1->prev->next=p2;
                        p1->prev=p2;
                }

                return head;
            }