1.Using c++ Write a function that has two linked-list head pointers as parameter
ID: 3670579 • Letter: 1
Question
1.Using c++ Write a function that has two linked-list head pointers as parameters. Assume that the linked list’s items are ordered by the < operator. On each list, every item is less than the next item on the same list. The function should create a new linked list that contains all the items on both lists, and the new linked list should also be ordered (so that every item is less than the next item on the list). The new linked list should also eliminate duplicate items (i.e., if the same item appears on both input lists, then only one copy is placed in the newly con- structed linked list). To eliminate duplicate items, you may assume that two items can be compared for equality using ==. The function should return a head pointer for the newly constructed linked list.
2. Write a function that starts with a single linked list of items and a special value called the splitting value. Two item values can be comparred using the < operator- but the items of the original linked list are in no particular order. The procedure divides the nodes into two linked lists: one containing alll the nodes that contain an item less than the splitting value, and one that contains all the other nodes. If the original linked list had any repeated items integers (ie, any two or more nodes with the same item in them) then the new linked list that has this item should have the same number of nodes that repeat this item. It does not matter whether you preserve the original linked list or destroy it in the process of building the two new lists, but your comments should documents what happens to the original linked list.
//Node Header file
#include <cstdlib> // Provides size_t and NULL
namespace main_savitch_5 {
class node {
public:
// TYPEDEF
typedef double value_type;
// CONSTRUCTOR
node(
const value_type &init_data = value_type(),
node *init_link = NULL
) {
data_field = init_data;
link_field = init_link;
}
// Member functions to set the data and link fields:
void set_data(const value_type &new_data) { data_field = new_data; }
void set_link(node *new_link) { link_field = new_link; }
// Constant member function to retrieve the current data:
value_type data() const { return data_field; }
// Two slightly different member functions to retreive
// the current link:
const node *link() const { return link_field; }
node *link() { return link_field; }
private:
value_type data_field;
node *link_field;
};
// FUNCTIONS for the linked list toolkit
std::size_t list_length(const node *head_ptr);
void list_head_insert(node *&head_ptr, const node::value_type &entry);
void list_insert(node *previous_ptr, const node::value_type &entry);
node *list_search(node *head_ptr, const node::value_type &target);
const node *list_search
(const node *head_ptr, const node::value_type &target);
node *list_locate(node *head_ptr, std::size_t position);
const node *list_locate(const node *head_ptr, std::size_t position);
void list_head_remove(node *&head_ptr);
void list_remove(node *previous_ptr);
void list_clear(node *&head_ptr);
void list_copy(const node *source_ptr, node *&head_ptr, node *&tail_ptr);
}
#endif
//CPP Node File
#include "node1.h"
#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL and size_t
using namespace std;
namespace main_savitch_5 {
size_t list_length(const node *head_ptr)
// Library facilities used: cstdlib
{
const node *cursor;
size_t answer;
answer = 0;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())
++answer;
return answer;
}
void list_head_insert(node *&head_ptr, const node::value_type &entry) {
head_ptr = new node(entry, head_ptr);
}
void list_insert(node *previous_ptr, const node::value_type &entry) {
node *insert_ptr;
insert_ptr = new node(entry, previous_ptr->link());
previous_ptr->set_link(insert_ptr);
}
node *list_search(node *head_ptr, const node::value_type &target)
// Library facilities used: cstdlib
{
node *cursor;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())
if (target == cursor->data())
return cursor;
return NULL;
}
const node *list_search(const node *head_ptr, const node::value_type &target)
// Library facilities used: cstdlib
{
const node *cursor;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())
if (target == cursor->data())
return cursor;
return NULL;
}
node *list_locate(node *head_ptr, size_t position)
// Library facilities used: cassert, cstdlib
{
node *cursor;
size_t i;
assert (0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != NULL); i++)
cursor = cursor->link();
return cursor;
}
const node *list_locate(const node *head_ptr, size_t position)
// Library facilities used: cassert, cstdlib
{
const node *cursor;
size_t i;
assert (0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != NULL); i++)
cursor = cursor->link();
return cursor;
}
void list_head_remove(node *&head_ptr) {
node *remove_ptr;
remove_ptr = head_ptr;
head_ptr = head_ptr->link();
delete remove_ptr;
}
void list_remove(node *previous_ptr) {
node *remove_ptr;
remove_ptr = previous_ptr->link();
previous_ptr->set_link(remove_ptr->link());
delete remove_ptr;
}
void list_clear(node *&head_ptr)
// Library facilities used: cstdlib
{
while (head_ptr != NULL)
list_head_remove(head_ptr);
}
void list_copy(const node *source_ptr, node *&head_ptr, node *&tail_ptr)
// Library facilities used: cstdlib
{
head_ptr = NULL;
tail_ptr = NULL;
// Handle the case of the empty list.
if (source_ptr == NULL)
return;
// Make the head node for the newly created list, and put data in it.
list_head_insert(head_ptr, source_ptr->data());
tail_ptr = head_ptr;
// Copy the rest of the nodes one at a time, adding at the tail of new list.
source_ptr = source_ptr->link();
while (source_ptr != NULL) {
list_insert(tail_ptr, source_ptr->data());
tail_ptr = tail_ptr->link();
source_ptr = source_ptr->link();
}
}
}
Explanation / Answer
node* Merge(const node *head1, const node *&head2)
{
node* newListHead = NULL;
//adding the head for new list
if (head1 == NULL && head2 == NULL)
{
return NULL;
}
else if (head1 == NULL)
{
newListHead = new node(head2->data, NULL);
}
else if (head2 == NULL)
{
newListHead = new node(head2->data, NULL);
}
else
{
if (head1->data < head2->data)
{
newListHead = new node(head1->data, NULL);
head1 = head1->link;
}
else if (head1->data > head2->data)
{
newListHead = new node(head2->data, NULL);
head2 = head2->link;
}
//if both nodes data is equal copy only one and move both of them to next node
else
{
newListHead = new node(head2->data, NULL);
head2 = head2->link;
head1 = head1->link;
}
}
node* temp = newListHead;
while (true)
{
if (head1 == NULL)
{
while (head2 != NULL)
{
list_insert(temp, head2->data);
temp = temp->link;
head2 = head2->link;
}
return newListHead;
}
else if (head2 == NULL)
{
while (head1 != NULL)
{
list_insert(temp, head1->data);
temp = temp->link;
head1 = head1->link;
}
return newListHead;
}
else
{
if (head1->data < head2->data)
{
list_insert(temp, head1->data);
temp = temp->link;
head1 = head1->link;
}
else if (head1->data > head2->data)
{
list_insert(temp, head2->data);
temp = temp->link;
head2 = head2->link;
}
//if both nodes data is equal copy only one and move both of them to next node
else
{
list_insert(temp, head2->data);
temp = temp->link;
head2 = head2->link;
head1 = head1->link;
}
}
}
}
node* split(node *head1, const node::value_type &splitting_value)
{
//I have not changed the original list and have created two new list one having values less than splitting value and //other having values greater than or equal to splitting_value
node* original = head1;
node* newListHead1 = NULL;
node* temp1 = newListHead1;
node* newListHead2 = NULL;
node* temp2 = newListHead2;
while (head1 != NULL)
{
if (original->data < splitting_value)
{
if (newListHead1 == NULL)
{
newListHead1 = new node(temp1->data, NULL);
temp1 = newListHead1;
}
else
{
list_insert(temp1, original->data);
}
original = original->link;
}
else
{
if (newListHead2 == NULL)
{
newListHead2 = new node(original->data, NULL);
temp2 = newListHead2;
}
else
{
list_insert(temp2, original->data);
}
original = original->link;
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.