Question

Merge two ordered singly linked lists of integers into one ordered list

in C++

Answer 1

Please find the required C++ script as the following:

//===============================================================

#include <bits/stdc++.h>

using namespace std;

// Node class to create linked list nodes

class Node

{

public:

int data;

Node* next;

};

// Shifting node from one list's front to other

void MoveNode(Node** destRef, Node** sourceRef);

// The main merging program

Node* SortedMerge(Node* a, Node* b)

{

Node dummy;

Node* tail = &dummy;

/* so tail->next is the place to

add new nodes to the result. */

dummy.next = NULL;

while (1)

{

if (a == NULL)

{

/* if either list runs out, use the

other list */

tail->next = b;

break;

}

else if (b == NULL)

{

tail->next = a;

break;

}

if (a->data <= b->data)

MoveNode(&(tail->next), &a);

else

MoveNode(&(tail->next), &b);

tail = tail->next;

}

return(dummy.next);

}

// MoveNode() moved node from the front of the source to the front of the destination

void MoveNode(Node** destRef, Node** sourceRef)

{

Node* newNode = *sourceRef; // The front node

assert(newNode != NULL);

*sourceRef = newNode->next; // Moving the soruce node

newNode->next = *destRef; // Link onld to new

*destRef = newNode; // Point destination to new node

}

// Add a node at the beginning of the linked list

void push(Node** head_ref, int new_data)

{

Node* new_node = new Node(); // Create node

new_node->data = new_data; // Add data

new_node->next = (*head_ref); // Add new node to the list

(*head_ref) = new_node; // Make new node as the head

}

// Print nodes of a list

void printList(Node *node)

{

while (node!=NULL)

{

cout<<node->data<<" ";

node = node->next;

}

}

// Driver program

int main()

{

// Empty initialization

Node* res = NULL;

Node* a = NULL;

Node* b = NULL;

// Two sample sorted list creation

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

// Merge removing duplicates

res = SortedMerge(a, b);

cout << "Merged Linked List is: \n";

printList(res);

return 0;

}

//=================================================================

output:

Merged Linked List is:
2 3 5 10 15 20