$//$ Linked Lists

struct node$\{$

int data;

node$*$ next;

$\}$

void add$\_$to$\_$end$($node$*$& head, int item$)$;

void remove$($node$*$& head, int target$)$;

int main$()\{$

node$*$ head;

$//$ mark the list as empty

head $=$ nullptr; $//$ NULL

$//$ add a node

head $=$ new node;

$//$ mark this as end of the list

$(*$head$).$next $=$ nullptr;

$(*$head$).$data $=5$;

$//$ add more nodes

$(*$head$).$next $=$ new node;

$(*(*$head$).$next$).$next $=$ nullptr;

$//$ same as line above

$//$ head $->$ next $->$ next $=$ nullptr;

$//$ Start the cursor at the first node

node$*$ cursor $=$ head;

$//$ Move cursor until it points to the last node $($NOT NULL$)$

while$($cursor $->$ next $!=$ nullptr$)\{$

cursor $=$ cursor $->$ next;

$\}$

$//$ Add a new node to the end of the list

cursor $->$ next $=$ new node;

cursor $->$ next $->$ next $=$ nullptr;

$//$ next $2$ do the same thing

$//$ cursor $=$ cursor $->$ next;

$//$ cursor $->$ next $=$ nullptr;

$//$ output everything in the list

cursor $=$ head;

while$($cursor $!=$ nullptr$)\{$

cout $<<$ cursor $->$ data $<<$ endl;

cursor $=$ cursor $->$ next;

$\}$

$//$ This line would cause a seg fault because cursor is pointing to NULL after the loop

cursor $->$ next $=$ new node;

add$\_$to$\_$end$($head$,9)$;

remove$($head$,5)$;

$\}$

void add$\_$to$\_$end$($node$*$& head, int item$)\{$

if$($head $==$ nullptr$)\{$

$//$ list is empty

head $=$ new node;

head $->$ next $=$ nullptr;

head $->$ data $=$ item;

return;

$\}$

node$*$ cursor $=$ head;

$//$ move cursor to last node

while$($cursor $->$ next $!=$ nullptr$)\{$

cursor $=$ cursor $->$ next;

$\}$

$//$ add new node

cursor $->$ next $=$ new node;

cursor $->$ next $->$ next $=$ nullptr;

cursor $->$ next $->$ data $=$ item;

$\}$

$/*$

What will this function do with an empty list?

$*/$

void remove$($node$*$& head, int target$)\{$

node$*$ cursor $=$ head;

node$*$ prev $=$ head;

if$($head $->$ data $==$ target$)\{$

head $=$ cursor $->$ next;

delete cursor;

return;

$\}$

$//$ move cursor to the target node

while$($cursor $!=$ nullptr && cursor $->$ data $!=$ target$)\{$

prev $=$ cursor;

cursor $=$ cursor $->$ next;

$\}$

if$($cursor $!=$ nullptr$)\{$

prev $->$ next $=$ cursor $->$ next;

delete cursor;

$\}$

else$\{$

cout $<<$ "Target not found

$"$;

$\}$

$\}$

or this lab you are to implement two functions, and I have given you the prototypes for the functions.

$$ The first function passes through the linked list and removes all duplicate items. You will need at least two, most likely three, additional pointers to pull this off. Remember that to remove an item you will need to hold onto the node before the one you are removing. When you are done, the total size of the linked list should be $<=500.$ I have given you a size function so you can check that. You should have the main call the show$\_$list function to print out this new smaller list.

$$ The second function takes the cleaned$-$up list, and a $$split value,$$ which is a number between $1$ and $500$ entered by the user. The function then creates two new lists, one having only numbers greater than the split value and one having only numbers less than the split value. The split value should not appear in either list. The sum of the size of these two lists should be equal to or one less than the cleaned$-$up list you built with the first function. $($The first function alters the original list, and this function creates two new lists.$)$

#include

#include

#include "header$\_$lab$6.$h$"$

using namespace std;

$//$ These are the three I have implemented for you which are

$//$ available in the header$\_$lab$6.$h file

$//$

$//$ void build$\_$list$($node$*$& head$)$; $//$ note that we are passing by reference

$//$ void show$\_$list$($const node$*$ head$)$;

$//$ int size$($const node$*$ head$)$;

$//$ These are the two that you are to write, as described in the instructions page.

$//$ Please write them as a part of the header$\_$lab$6.$h file.

$//$

$//$ void remove$\_$repeats$($node$*$& head$)$;

$//$ void split$\_$list$($const node$*$ original, node$*$& lesser, node$*$& greater, int split$\_$value$)$;

$//$ Feel free to edit the main as much as you like for debugging.

$//$ Please run the command 'make run$\_$tests' to test your code before submitting.

int main$()\{$

int start, stop;

int split;

node$*$ head $=$ NULL;

node$*$ lesser;

node$*$ greater;

start $=$ time$($NULL$)$;

build$\_$list$($head$)$;

stop $=$ time$($NULL$)$;

cout $<<$ "Time to build list $="<<$ stop $-$ start $<<$ "seconds.

$"$;

start $=$ time$($NULL$)$;

show$\_$list$($head$)$;

stop $=$ time$($NULL$)$;

cout $<<$ "Time to print list $="<<$ stop $-$ start $<<$ "seconds.

$"$;

cout $<<$ "Size of the list $="<<$ size$($head$)<<$ endl;

return $0$;

$\}$