Insérer un Nœud dans une liste Doublement chaînée Triée

Je ne suis pas en mesure de comprendre, pourquoi mon code pour l'insérer dans un triée liste doublement liée à défaut sur certains cas de test.S'il vous plaît laissez-moi savoir. Je ne sais pas du cas de test, ils sont générés par le système.

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

Grâce

Vous pouvez être intéressé par la façon dont cela peut être fait en utilisant de manière significative une approche différente à l'aide d'un pointeur de pointeur de marcher sur la réelle pointeurs dans votre liste plutôt que de simplement les nœuds (des sons étranges, je sais, mais ce qui a considérablement réduit l'algorithme). Voir en direct.
Dans le code, pourquoi est-pp un pointeur de pointeur vers le nœud? Peut pas être accompli en utilisant un pointeur vers le nœud?
certes, la raison pour laquelle je préfère que l'algorithme est franchement en raison de sa simplicité. En fin de compte la mi-insertion dans une liste, implique la mise à jour nœud existant pointeurs. Je préfère utiliser le pointeurs dans la liste plutôt que d'avoir à gérer d'autres inutilement.

InformationsquelleAutor Vansh Khurana | 2013-12-01

algorithm c++

Une fois que vous atteignez le dernier nœud, vous devriez comparer ses données avec le nouveau nœud et l'insérer en conséquence.

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

Si l'exécution atteint cette partie, alors, à présent curr vers le dernier nœud. Maintenant vous devriez comparer ses données comme suit:

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

Merci pour le bug!

InformationsquelleAutor Abhishek Bansal

Alternativement, vous pouvez écrire une condition if pour le nœud à la fin de la liste

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;

}

InformationsquelleAutor Ruthwik

/*
* For reference:
*
* link to the problem :- 
* https://www.hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list
*
* DoublyLinkedListNode {
*     int data;
*     DoublyLinkedListNode* next;
*     DoublyLinkedListNode* prev;
* };
*
* Function to insert a node in sorted DLL with given data & return head 
*/
DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* head, int data) {
    DoublyLinkedListNode** prev = &head;
    DoublyLinkedListNode* newNode = new DoublyLinkedListNode(data);

    while ( *prev && ((*prev)->data <= data) ) {
        prev = &(*prev)->next;
    }

    newNode->prev = *prev;
    newNode->next = *prev;
    *prev = newNode;

    return head;
}

Cette solution fonctionne dans tous les cas (insérer entre les, insérer, à la tête, insérer, à la fin, etc). J'essayais juste d'écrire un code sans conditions. Alors que la recherche d'une erreur, je suis tombé sur ce fil. Ne corrigez-moi si cette solution ne fonctionne pas pour certains cas de test.

InformationsquelleAutor despicable_me

-1

Voici un peu de code pour Insérer un Nœud dans Triés Liste Doublement chaînée

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

InformationsquelleAutor Amin Elsehemy

-1

Voici la programme en C++ pour l'insertion d'un nœud à la bonne position dans un classement liste doublement chaînée:

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

InformationsquelleAutor RBT

-2

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

Une réponse entièrement composé de code n'est pas l'idéal. Veuillez fournir des framing ou l'explication des points clés de votre réponse.

InformationsquelleAutor Pranav Kumar

Vous devez vous connecter pour publier un commentaire.