The Problem Complete the mergeList function that accepts two node * (the heads o

Question

The Problem

Complete the mergeList function that accepts two node * (the heads of two linked lists). This function must merge the two linked lists by interleaving their nodes, starting with the first list. If one list is longer than the other, the extra nodes should not be interleaved.

For example:

This must be done without allocating any nodes (eg: you should never use the new word, you must rearrange the memory that has already been allocated).

A main function has been provided that tests your mergeList function.

//main.cpp

#include <iostream>

using namespace std;

struct node {

int val;

node *next;

};

void printList(node *head) {

if (head == NULL) {

cout << "Empty list" << endl;

return;

}

node *temp = head;

int count = 0;

while(temp != NULL) {

cout << "Node " << count << ": " << temp ->val << endl;

count++;

temp = temp->next;

}

}

void mergeList(node *first, node *second) {

// your code here

}

int main() {

// Example #1

node n0, n2, n4, n11, n33, n55;

n0.val = 0;

n2.val = 2;

n4.val = 4;

n11.val = 11;

n33.val = 33;

n55.val = 55;

n0.next = &n2;

n2.next = &n4;

n4.next = NULL;

n11.next = &n33;

n33.next = &n55;

n55.next = NULL;

cout<<"First List:"<<endl;

printList(&n0);

cout<<"Second List:"<<endl;

printList(&n11);

mergeList(&n0, &n11);

cout<<"Merged List:"<<endl;

printList(&n0);

cout<<endl;

// Example #2

node p0, p2, p11, p33, p33_2, p44;

p0.val = 0;

p2.val = 2;

p11.val = 11;

p33.val = 33;

p33_2.val = 33;

p44.val = 44;

p0.next = &p2;

p2.next = NULL;

p11.next = &p33;

p33.next = &p33_2;

p33_2.next = &p44;

p44.next = NULL;

cout<<"First List:"<<endl;

printList(&p0);

cout<<"Second List:"<<endl;

printList(&p11);

mergeList(&p0, &p11);

cout<<"Merged List:"<<endl;

printList(&p0);

return 0;

}

Explanation / Answer

#include<stdio.h>
#include<stdlib.h>

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

struct node* SortedMerge(struct node* a, struct node* b)
{
struct node dummy;

struct node* tail = &dummy;

dummy.next = NULL;
while (1)
{
if (a == NULL)
{
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);
}


void MoveNode(struct node** destRef, struct node** sourceRef)
{
struct node* newNode = *sourceRef;
*sourceRef = newNode->next;
newNode->next = *destRef;
*destRef = newNode;
}


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

new_node->data = new_data;

new_node->next = (*head_ref);

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

int main()
{
struct node* res = NULL;
struct node* a = NULL;
struct node* b = NULL;


push(&a, 15);
push(&a, 10);
push(&a, 5);

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

res = SortedMerge(a, b);

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

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.