Problem 4 [18 marks] Complete the following three linked list functions accordin

Question

Problem 4 [18 marks] Complete the following three linked list functions according to the provided specifications. Use full C code. You may use the LL-node.h and LLh files online as starting points In all cases, you should assume that a linked list data type is composed of two fields, a pointer to the head node, a pointer to the tail node, but both NULLifempty. Each node contains two fields: its value data and a pointer to the next node in the chain. Assume all linked lists and node sequences are valid. In addition, you should write a main function that creates test cases for each function. Choose your test cases wisely such that you will have good "test coverage For example, in the reverse (L) function described below, it may be a good idea to write a test for an empty as well as a non-empty list. Sample tests for the reverse (L) function can look something like: L 42 36 14 17 48 361 reverse (L) L (36 48 17 14 36 42 Reverse (L) [1 Once again, please include a screenshot of the execution of your code. The following input list L will be used for the examples below: NULL tail:

Explanation / Answer

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

// value and next pointer in struct creating a node
typedef struct node {
int value;
struct node *next;
}LL_t;

LL_t *head = NULL, *tail = NULL;
void insert(int data){
if (head == NULL) {
head = tail = malloc(sizeof(LL_t));
head->value = data;
head->next = NULL;
return;
}
tail->next = malloc(sizeof(LL_t));
tail = tail->next;
tail->value = data;
tail->next = NULL;
}

void print(LL_t *L){
printf("[");
while (L!= NULL)
{
printf("%d ", L->value);
L = L->next;
}
printf("] ");
}

void reverse(LL_t *L){
if(L->next == NULL){
tail = head = L;
return;
}
reverse(L->next);
tail->next = L;
tail = tail->next;
tail->next = NULL;
}

unsigned int removeNumber(LL_t *L, int target){
LL_t *cur = L, *prev = L;
int count = 0;
while(cur != NULL){
if(cur->value == target){
// if its head node value
++count;
if(head == cur){
head = prev = cur->next;
free(cur);
}else{
prev->next = cur->next;
free(cur);
cur = prev;
}
}else{
prev = cur;
cur = cur->next;
}
}
tail = prev;
return count > 0?0:1;

}

void merge(LL_t *L1, LL_t *L2){
LL_t *head1 = NULL, *tail1 = NULL;
while(L1 != NULL || L2 != NULL){
if(L1 == NULL){
if(head1 == NULL){
head1 = tail1 = L2;
}else{
tail1->next = L2;
tail1 = tail1->next;
}
L2 = L2->next;
}
else if(L2 == NULL){
if(head1 == NULL){
head1 = tail1 = L1;
}else{
tail1->next = L1;
tail1 = tail1->next;
}
L1 = L1->next;
}else{
if(L1->value <= L2->value){
if(head1 == NULL){
head1 = tail1 = L1;
}else{
tail1->next = L1;
tail1 = tail1->next;
}
L1 = L1->next;
}else{
if(head1 == NULL){
head1 = tail1 = L2;
}else{
tail1->next = L2;
tail1 = tail1->next;
}
L2 = L2->next;
}
}
}
L1 = head1;
free(L2);
}

int main(){
// value to check for this list
int value[] = {42, 36, 14, 17, 48, 36};
for(int i = 0;i < 6;++i){
insert(value[i]);
}
printf("List after insetion: ");
print(head);
reverse(head);
printf("List after reverse: ");
print(head);
removeNumber(head, 42);
printf("List after removing 42: ");
print(head);
print(head);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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