Project Description: Use pointer linked-list to implement the following. Write a
ID: 3531695 • Letter: P
Question
Project Description:
Use pointer linked-list to implement the following.
Write a program that merges two ordered lists of objects of integers into a single ordered list object of integers.
The lists are in ascending order. The resulting list is also in ascending order. Ask user for the two ordered lists
(input from keyboard). Function "merge_lists(...)" should receive reference to each of the list objects (i.e.
passed-by-reference) to be merged and reference to a list object into which the merged elements will be replaced (i.e.
the function returns a pointer to the head of a new linked list that contains all of the nodes in the original two lists.
The nodes in this longer list are also sorted from smallest to largest values.)
Example:
List A contains 3,5,6,10
List B contains 1,4,5,7,10,11
Emerged list C contains 1,3,4,5,5,6,7,10,10,11 (in this order)
Explanation / Answer
/*Here is the correct c++ code*/
/*Program to alternatively split a linked list into two halves */
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include <iostream>
using namespace std;
/* Link list node */
struct node
{
int data;
struct node* next;
};
/* pull off the front node of the source and put it in dest */
void MoveNode(struct node** destRef, struct node** sourceRef);
/* Takes two lists sorted in increasing order, and splices their nodes together to make one big sorted list which is returned. */
struct node* SortedMerge(struct node* a, struct node* b)
{
/* a dummy first node to hang the result on */
struct node dummy;
/* tail points to the last result node */
struct 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);
}
/* UTILITY FUNCTIONS */
/*MoveNode() function takes the node from the front of the source, and move it to the front of the dest.
It is an error to call this with the source list empty.
Before calling MoveNode():
source == {1, 2, 3}
dest == {1, 2, 3}
Affter calling MoveNode():
source == {2, 3}
dest == {1, 1, 2, 3}
*/
void MoveNode(struct node** destRef, struct node** sourceRef)
{
/* the front source node */
struct node* newNode = *sourceRef;
assert(newNode != NULL);
/* Advance the source pointer */
*sourceRef = newNode->next;
/* Link the old dest off the new node */
newNode->next = *destRef;
/* Move dest to point to the new node */
*destRef = newNode;
}
/* Function to insert a node at the beginging 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)
{
cout<<node->data;
node = node->next;
}
}
/* 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 shall be 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);
cout<<" Merged Linked List is: ";
printList(res);
getchar();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.