3.cpp File Reference

#include <iostream>
#include <string>
#include <sstream>

Include dependency graph for 3.cpp:

Go to the source code of this file.

Classes
struct	Node

Functions
void	build_sorted_linkedlist (Node *&headptr1, int input)
Node *	last_node_greater_than (Node *currentptr, int input)
void	linkedlist_int (Node *&headptr1)
int	main ()
void	print_linked_list (Node *headptr1)
void	recursive_remove_dups (Node *headptr1)
void	remove_dups_negative_nums (Node *&headptr1)

Function Documentation

build_sorted_linkedlist()

void build_sorted_linkedlist	(	Node *&	headptr1,
		int	input )

Definition at line 11 of file 3.cpp.

                                                          {
    // insert a new item 'input' into an existing sorted linked list
    // with head pointer headptr1
    Node * previous = headptr1;
    if (previous != nullptr) {
        if (previous->value < input) {
            while (previous->nextptr != nullptr) {
                if (previous->nextptr->value < input) {
                    previous = previous->nextptr;
                }
                else break;
            }
            Node * next = previous->nextptr;
            Node * current = new Node;
            previous->nextptr = current;
            current->value = input;
            current->nextptr = next;
        }
        else {
            // the input is smaller than the first item in the linked list
            headptr1 = new Node;
            headptr1->value = input;
            headptr1->nextptr = previous;
            // the input becomes the new headptr
        }
    }
    else {
        // the first linked list is blank, so we create one
        // since we need to insert something
        headptr1 = new Node;
        headptr1->value = input;
        headptr1->nextptr = nullptr;
    }
}

References Node::nextptr, and Node::value.

Referenced by linkedlist_int(), and main().

Here is the caller graph for this function:

last_node_greater_than()

Node * last_node_greater_than	(	Node *	currentptr,
		int	input )

Definition at line 110 of file 3.cpp.

                                                            {
    if (currentptr != nullptr) {
        if (currentptr->nextptr != nullptr) {
            if (currentptr->nextptr->value > input) {
                return currentptr;
            }
            else {
                Node * result = last_node_greater_than(currentptr->nextptr, input);
                if (result == nullptr) {
                    return currentptr;
                }
                else {
                    return result;
                }
            }
        }
        else {
            if (currentptr->value <= input) {
                return currentptr;
            }
            else {
                return nullptr; // currentptr->value is greater than input
                // so last_node_greater_than should be previous node
            }
        }
    }
    else {
        return nullptr; // uninitialized linked list
    }
}

References last_node_greater_than(), Node::nextptr, and Node::value.

Referenced by last_node_greater_than().

Here is the call graph for this function:

Here is the caller graph for this function:

linkedlist_int()

void linkedlist_int

(

Node *&

headptr1

)

Definition at line 46 of file 3.cpp.

                                      {
    // we expect headptr1 to be nullptr
    // otherwise, we will have memory leak!
    string line;
    getline(cin, line);
    istringstream line_in(line);
    // the first input
    int x;
    if (line_in >> x) {
        headptr1 = new Node;
        headptr1->value = x;
        headptr1->nextptr = nullptr;
        // subsequent inputs
        int input;
        while (line_in >> input) {
            build_sorted_linkedlist(headptr1, input);
        }
    }
    return;
}

References build_sorted_linkedlist(), Node::nextptr, and Node::value.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

main()

int main

(

void

)

Definition at line 157 of file 3.cpp.

           {
    Node * node1head = nullptr;
    Node * node2head = nullptr;
    linkedlist_int(node1head);
    print_linked_list(node1head);
    linkedlist_int(node2head);
    print_linked_list(node2head);
    // merge sort
    Node * current = node2head;
    while (current != nullptr) {
        build_sorted_linkedlist(node1head, current->value);
        current = current->nextptr;
    }
    remove_dups_negative_nums(node1head);
    //recursive_remove_dups(node1head);
    print_linked_list(node1head);
    return 0;
}

References build_sorted_linkedlist(), linkedlist_int(), Node::nextptr, print_linked_list(), remove_dups_negative_nums(), and Node::value.

Here is the call graph for this function:

print_linked_list()

void print_linked_list

(

Node *

headptr1

)

Definition at line 67 of file 3.cpp.

                                        {
    // print all stuffs
    Node * current_node = headptr1;
    while (current_node != nullptr) {
        cout << current_node->value;
        current_node = current_node->nextptr;
        if (current_node == nullptr) {
            break;
        }
        cout << " ";
    }
    cout << endl;
}

References Node::nextptr, and Node::value.

Referenced by main().

Here is the caller graph for this function:

recursive_remove_dups()

void recursive_remove_dups

(

Node *

headptr1

)

Definition at line 141 of file 3.cpp.

                                            {
    // headptr1 linked list must be sorted ascendingly
    if (headptr1 == nullptr) {
        return;
    }
    if (headptr1->nextptr != nullptr) {
        if (headptr1->value == headptr1->nextptr->value) {
            headptr1->nextptr = headptr1->nextptr->nextptr;
            recursive_remove_dups(headptr1);
        }
        else {
            recursive_remove_dups(headptr1->nextptr);
        }
    }
}

References Node::nextptr, recursive_remove_dups(), and Node::value.

Referenced by recursive_remove_dups().

Here is the call graph for this function:

Here is the caller graph for this function:

remove_dups_negative_nums()

void remove_dups_negative_nums

(

Node *&

headptr1

)

Definition at line 81 of file 3.cpp.

                                                 {
    // headptr1 linked list must be sorted ascendingly
    Node * current = headptr1;
    while (current != nullptr && current->nextptr != nullptr) {
        if (current->value == current->nextptr->value) {
            // 1 2 x x 6 7
            // remove the second occurrence of x as duplicate
            Node * next = current->nextptr;
            current->nextptr = next->nextptr;
            delete next;
        }
        else {
            current = current->nextptr;
        }
    }
    // since the list is sorted, the negative values are
    // located at the beginning of the list
    while (headptr1 != nullptr) {
        if (headptr1->value < 0) {
            Node * next = headptr1;
            headptr1 = headptr1->nextptr; // set the new head pointer
            delete next; // free up memory
        }
        else {
            break;
        }
    }
}

References Node::nextptr, and Node::value.

Referenced by main().

Here is the caller graph for this function: