Question

In: Computer Science

C++ Question Create two circular linked lists and find their maximum numbers. Merge the two circular...

C++ Question

Create two circular linked lists and find their maximum numbers. Merge the two circular linked lists such that the maximum number of 2nd circular linked list immediately follows the maximum number of the 1st circular linked list.

Input:

12 -> 28 -> 18 -> 25 -> 19-> NULL

5 -> 24 -> 12 -> 6 -> 15-> NULL

Output:

28 -> 24-> 25 -> 15 -> 19 -> 15->5-> 18 -> 25 -> 19->NULL

Note:- Code should work on MS-Visual studio 2017 and provide output along with code

Solutions

Expert Solution

class Node

{

public:

int data;

Node* next;

};

/* pull off the front node of

the source and put it in dest */

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

/* Takes two lists sorted in increasing

order, and splices their nodes together

to make one big sorted list which

is returned. */

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

{

/* a dummy first node to hang the result on */

Node dummy;

/* tail points to the last result node */

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(Node** destRef, Node** sourceRef)

{

/* the front source node */

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(Node** head_ref, int new_data)

{

/* allocate node */

Node* new_node = new 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(Node *node)

{

while (node!=NULL)

{

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

node = node->next;

}

}

/* Driver code*/

int main()

{

/* Start with the empty list */

Node* res = NULL;

Node* a = NULL;

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

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

printList(res);

return 0;

}


Related Solutions

Write a C++ code to insert the following numbers in two Linked Lists. Insert numbers of...
Write a C++ code to insert the following numbers in two Linked Lists. Insert numbers of first list in Linked List#1, and numbers of second list in Linked List#2. Do not insert both lists in a single Linked List. List#1. 5, 78, 45, 23, 11, 89, 10, 78, 6, 99, 876, 5, 67, 13 List#2. 5, 89, 688, 52, 557, 953, 5, 7, 55, 35, 89, 99, 99, 6, 557, 89, 5, 99, 6, 2, 45, 12, 7, 6, 94,...
Given two sorted linked lists, merge them into a third sorted linked list. If an element...
Given two sorted linked lists, merge them into a third sorted linked list. If an element is present in both the lists, it should occur only once in the third list. Code needed in java.
Using C++, you will create a program, where you will create two doubly linked lists. These...
Using C++, you will create a program, where you will create two doubly linked lists. These doubly linked lists will contain integers within them. Using the numbers in both of these linked lists, you add the numbers together, and insert the addition of the two numbers into a singly linked list. the input can be from the user or you just write the input. for example, if one number in the doubly linked list is 817 and in the other...
C++ Linked Lists Practice your understanding of linked lists in C++ by creating a list of...
C++ Linked Lists Practice your understanding of linked lists in C++ by creating a list of songs/artist pairs. Allow your user to add song / artist pairs to the list, remove songs (and associated artist) from the list and be sure to also write a function to print the list! Have fun! Make sure you show your implementation of the use of vectors in this lab (You can use them too ) You MUST modularize your code ( meaning, there...
In python i want to create a function. The function will take in two linked lists...
In python i want to create a function. The function will take in two linked lists as the parameters. If one is shorter than the other then the shorter will be the length. I want to take the values from both linked lists and turn them into tuples. I then want these tuples to be put into a new linked list. I want to return that linked list. I want to do this using recursion and no helper functions or...
"C language" Take this code and make the minor modification necessary to create a circular linked...
"C language" Take this code and make the minor modification necessary to create a circular linked list (Hint: Store a pointer to the first node in the next pointer of the last node.) Demonstrate that this is working by traversing the list until the first pointer is encountered 3 times. Next redefine the node structure to include a back pointer. This will enable your program to move from front to back and then from back to front. It is not...
create a function to merge and concatenate two linked list l1 =[1,2,4] and l2=[1,3,4]. dont modify...
create a function to merge and concatenate two linked list l1 =[1,2,4] and l2=[1,3,4]. dont modify l2 (the nodes inserted in l1 should be copies of l2 class Node(object): def __init__(self, data): self.data = data self.next = None    class LinkedList(object): def print_list(self): cur_node = self.head while cur_node: print(cur_node.data) cur_node = cur_node.next def __init__(self): self.head = None;    def append(self, data): new_node = Node(data) if self.head is None: self.head = new_node return last_node = self.head while last_node.next: last_node = last_node.next...
Data Structures Homework – Singly Linked Lists Create a singly linked that represents a school. The...
Data Structures Homework – Singly Linked Lists Create a singly linked that represents a school. The school has multiple classes. Each class has a different number of students. class student { Long ID; string Name; string Address; float grades[3]; student *below; }; class Node // the node represents a class in school { int ID; int NoOfStudents; int NoOfQuizes; student *t;// a linked list of students is allocated dynamically Node *Next; }; class school { string Name; Node *Head; int...
In C++ Use vectors instead of linked lists Create a Hash table program using H(key) =...
In C++ Use vectors instead of linked lists Create a Hash table program using H(key) = key%tablesize with Chaining and Linear probing for a text file that has a list of 50 numbers Ask the user to enter the file name, what the table size is, and which of the two options they want to use between chaining and linear probing
Working with Linked Lists in C++ Tasks As stated in the objectives, you have two methods...
Working with Linked Lists in C++ Tasks As stated in the objectives, you have two methods to implement. These methods (which contain TODO comments) are found in linked_list.cpp. Part 1 Implement the copy constructor; use the LinkedBag as inspiration for your solution as the technique of creating a deep copy is essentially the same. Part 2 Implement the replace method. //linked_list.cpp #include "linked_list.h" // Header file #include <cassert> template<class Object> LinkedList<Object>::LinkedList() : headPtr( nullptr ), itemCount( 0 ) { }...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT