mercredi 20 juin 2018

C++, Pointers, Merging of two sorted linked lists

I took reference of code from GeeksForGeeks for merging of two sorted linked lists.

#include <bits/stdc++.h>
using namespace std;

/* Link list node */
struct Node
{
    int data;
    struct Node* next;
};

void MoveNode(Node **destRef, Node **sourceRef){
    cout << "pp: " << (*sourceRef) << endl;
    Node *tempNode = *sourceRef;

    cout << "tt:" << tempNode->next << endl;
    *sourceRef = tempNode->next;

    tempNode->next = *destRef;

    *destRef = tempNode;
    cout << "qq: " << (*sourceRef) << endl;

}

struct Node* SortedMerge(Node *a, Node *b){
    Node *dummy;
    Node *tail;
    dummy->next = NULL;
    tail = dummy;
    cout << "hii" << endl;

    while(true){
        if(a==NULL){
            cout << "aa" << endl;
            tail->next = b;
            break;
        }
        else if(b==NULL){
            cout << "bb" << endl;
            tail->next = a;
            break;
        }

        if(a->data < b->data){
            cout << "cc" << endl;
            MoveNode(&(tail->next), &a);
            tail = tail->next;
        }
        else if(a->data >= b->data){
            cout << "dd" << endl;
            // cout << "b->data: " << b << endl;
            MoveNode(&(tail->next), &b);
            // b = b->next;
            // cout << "b->data: " << b << endl;
            // cout << "b->data: " << b->data << endl;
            tail = tail->next;
        }
    }
    return dummy->next;
}


/* Function to insert a node at the beginning of the
   linked list */
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node =
        (struct Node*) malloc(sizeof(struct Node));

    /* put in the data  */
    new_node->data  = new_data;

    /* link the old list off the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}

/* Function to print nodes in a given linked list */
void printList(struct Node *node)
{
    while (node!=NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
    cout << endl;
}

/* Drier program to test above functions*/
int main()
{
    /* Start with the empty list */
    struct Node* res = NULL;
    struct Node* a = NULL;
    struct Node* b = NULL;

    /* Let us create two sorted linked lists to test
      the functions
       Created lists, a: 5->10->15,  b: 2->3->20 */
    push(&a, 15);
    push(&a, 10);
    push(&a, 5);

    push(&b, 20);
    push(&b, 3);
    push(&b, 2);

    /* Remove duplicates from linked list */
    res = SortedMerge(a, b);

    printf("Merged Linked List is: \n");
    printList(res);

    return 0;
}

For the given example in the main function, the program gives wrong output if I do not print the node values in the second else if of while loop in SortedMerge function. And if I do print them the program gives correct output. I find it very strange. Can someone please help me out?

Aucun commentaire:

Enregistrer un commentaire