DPST1091 Revision Linked Lists Sample Solutions

Download most_frequent_list.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/25T1/activities/most_frequent_list/most_frequent_list.c .

Your task is to add code to this function in most_frequent_list.c:

// return the value which occurs most frequently in a linked list
// if several values are equally most frequent
// the value that occurs earliest in the list is returned
int most_frequent(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return 42;

}

struct node {
    struct node *next;
    int          data;
};

Add code to most_frequent so that its returns the most frequently occurring value in the linked list.

For example if the linked list contains these 8 elements:

655 10 204 8192 76 38 204 43912 204

most_frequent should return 204, because it is the most frequently occurring integer -- it appears 3 times.

For example if the linked list contains these 8 elements:

7 8 12 3 12 3 8

most_frequent should return 8.

There is a tie for most frequently occurring integer - 3, 8 and 12 all occur twice.

8 occurred first in the list so it should be returned.

You are not permitted to use arrays or malloc in your function.

Testing

This main function:

• converts the command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls most_frequent(head)
• prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your most_frequent function will be called directly in marking. The main function is only to let you test your most_frequent function

Here is how you the main function allows you to test most_frequent:

cp -n /import/reed/A/dp1091/public_html/25T1/activities/most_frequent_list/most_frequent_list.c .
dcc most_frequent_list.c -o most_frequent_list
./most_frequent_list 655 10 204 8192 76 38 204 43912 204
204
./most_frequent_list 5 4 6 5 4 6
5
./most_frequent_list 3 5 7 11 13 15 3 17 19 23 29 13 3
3

Assumptions/Restrictions/Clarifications.

most_frequent should not change the linked list it is given. Your function should not change the next or data fields of list nodes.

most_frequent should not use arrays.

most_frequent should not call malloc.

most_frequent should not call scanf (or getchar or fgets).

You can assume the linked list contains at least one integer.

most_frequent should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1091 autotest most_frequent_list

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

struct node {
    struct node *next;
    int          data;
};

struct node *strings_to_list(int len, char *strings[]);
int most_frequent(struct node *head);
int count_occurrances(int i, struct node *head);

int main(int argc, char *argv[]) {
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    int result = most_frequent(head);
    printf("%d\n", result);

    return 0;
}

// return the value which occurs most frequently in a linked list
// if several values are equally most frequent
// the value that occurs earliest in the list is returned
int most_frequent(struct node *head) {
    int most_frequent_num = 0;
    int most_frequent_count = 0;
    struct node *p = head;
    while (p != NULL) {
        int count = count_occurrances(p->data, head);
        if (count > most_frequent_count) {
            most_frequent_num = p->data;
            most_frequent_count = count;
        }
        p = p->next;
    }
    return most_frequent_num;
}

// return the number of times i, occurs in a linked list
int count_occurrances(int i, struct node *head) {
    int num = 0;
    struct node *p = head;
    while (p != NULL) {
        if (p->data == i) {
            num = num + 1;
        }
        p = p->next;
    }
    return num;
}


// DO NOT CHANGE THIS FUNCTION

// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

Download list_product.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/25T1/activities/list_product/list_product.c .

Your task is to add code to this function in list_product.c:

// product should return the sum of the elements in list1 multiplied by 
// the corresponding element in list2
// if one list is longer than the other, the extra list elements are ignored 
int product(struct node *head1, struct node *head2) {

    // PUT YOUR CODE HERE (change the next line!)
    return 42;

}

struct node {
    struct node *next;
    int          data;
};

product should return the sum of the elements in the first list multiplied by the corresponding element in the second list.

If one list is longer than the other, the extra elements should be ignored.

For example, if the two lists contain these values:

list1: 3, 1, 4, 1, 5, 9

list2: 2, 7, 9

product should return 49, because 3 * 2 + 1 * 7 + 4 * 9 = 49 .

For example, if the two lists contain these values:

list1: 2, 7

list2: 4, 42, 4242, 4242, 4242424242

product should return 302, because 2 * 4 + 7 * 42 = 302.

Testing

This main function:

• uses a command line argument of "-" to separate the values for two linked lists.
• converts the command-line arguments before the "-" to a linked list
• assigns a pointer to the first node in the linked list to head1
• converts the command-line arguments after the "-" to a linked list
• assigns a pointer to the first node in the linked list to head2
• calls product(head1, head2)
• prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your product function will be called directly in marking. The main function is only to let you test your product function

Here is how the main function allows you to test product:

dcc list_product.c -o list_product
./list_product 3 1 4 1 5 9 - 2 7 9 8
57
./list_product 16 7 8 12 - 13 19 21 12
653
./list_product 2 4 6 - 42
84
./list_product - 1 2 3 4
0
./list_product 4 3 2 1 -
0
./list_product -
0

Assumptions/Restrictions/Clarifications.

The data fields of the lists may contain any integer.

product should return only a single integer.

product should not change the linked lists it is given.

product should not change the next or data fields of list nodes.

product should not use arrays.

product should not call malloc.

product should not call scanf (or getchar or fgets).

product should not print anything. It should not call printf.

Do not change the definition of struct node.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1091 autotest list_product

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

struct node {
    struct node *next;
    int          data;
};

int product(struct node *head1, struct node *head2);
int member(int i, struct node *head);
struct node *strings_to_list(int len, char *strings[]);

int main(int argc, char *argv[]) {
    // create two linked lists from command line arguments
    int dash_arg = argc - 1;
    while (dash_arg > 0 && strcmp(argv[dash_arg], "-") != 0) {
        dash_arg = dash_arg - 1;
    }
    struct node *head1 = strings_to_list(dash_arg - 1, &argv[1]);
    struct node *head2 = strings_to_list(argc - dash_arg - 1, &argv[dash_arg + 1]);

    int result = product(head1, head2);
    printf("%d\n", result);

    return 0;
}


// product should the sum of the elements in list1 multiplied by 
// the corresponding element in list2
// if one list is longer than the other, the extra list elements are ignored 
int product(struct node *head1, struct node *head2) {
	if (!head1 || !head2) {
		return 0;
	} else {
		return (head1->data * head2->data) + product(head1->next, head2->next);
	}
}



// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

Download list_count_matches.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/25T1/activities/list_count_matches/list_count_matches.c .

Your task is to add code to this function in list_count_matches.c:

// Return the number of matches in the two lists, i.e. the number of
// values which occur at the same position in both linked lists.
int count_matches(struct node *head1, struct node *head2) {

    // PUT YOUR CODE HERE (change the next line!)
    return 42;

}

struct node {
    int          data;
    struct node *next;
};

// Return the number of matches in the two lists, i.e. the number of
// values which occur at the same position in both linked lists.
int count_matches(struct node *head1, struct node *head2) {

    // PUT YOUR CODE HERE (change the next line!)
    return 42;

}

Add code to count_matches so that returns a count of how many places the two lists have the same value in the same position.

For example, if the two lists contain these values:

1, 4, 1, 5, 9, 2, 1, 8
1, 1, 8, 2, 9, 5

count_matches should return 2 because both lists have the same value (1) at position 0 and the same value (9) at position 4.

Note: the lists may be any length and the two lengths may be unequal.

Testing

This main function:

• uses a command line argument of "-" to separate the values for two linked lists.
• converts the command-line arguments before the "-" to a linked list
• assigns a pointer to the first node in the linked list to head1
• converts the command-line arguments after the "-" to a linked list
• assigns a pointer to the first node in the linked list to head2
• calls count_matches(head1, head2)
• prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your count_matches function will be called directly in marking. The main function is only to let you test your count_matches function

Here is how the main function allows you to test count_matches:

dcc -o list_count_matches list_count_matches.c
./list_count_matches 3 1 4 - 2 7 1 8 3
0
./list_count_matches 1 2 3 4 - 2 1 3 8
1
./list_count_matches 5 5 6 5 - 6 5 5 5
2
./list_count_matches 3 5 7 - 3 5 19 7 23 29
2
./list_count_matches 1 2 3 4 5 6 - 3 2 1
1
./list_count_matches - 1 2 3 4
0
./list_count_matches 4 3 2 1 -
0
./list_count_matches -
0

Assumptions/Restrictions/Clarifications.

The linked lists may be of unequal lengths.

The linked lists may be any length.

Either or both linked lists may be empty (contain no elements).

count_matches should not change the linked lists it is given. Your function should not change the next or data fields of list nodes.

count_matches should not use arrays.

count_matches should not call malloc.

count_matches should not call scanf (or getchar or fgets).

count_matches should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1091 autotest list_count_matches

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

struct node {
    struct node *next;
    int          data;
};


// Return the number of matches in the two lists, i.e. the number of
// values which occur at the same position in both linked lists.
int count_matches(struct node *head1, struct node *head2) {

    int count = 0;
    while (head1 != NULL&& head2 != NULL) {
        if (head1->data == head2->data) {
            count++;
        }

        head1 = head1->next;
        head2 = head2->next;

    }

    // PUT YOUR CODE HERE (change the next line!)
    return count;

}

// You should not change any of the code below.

int count_matches(struct node *head1, struct node *head2);
struct node *strings_to_list(int len, char *strings[]);

// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
    // create two linked lists from command line arguments
    int dash_arg = argc - 1;
    while (dash_arg > 0 && strcmp(argv[dash_arg], "-") != 0) {
        dash_arg = dash_arg - 1;
    }
    struct node *head1 = strings_to_list(dash_arg - 1, &argv[1]);
    struct node *head2 = strings_to_list(argc - dash_arg - 1, &argv[dash_arg + 1]);

    int result = count_matches(head1, head2);
    printf("%d\n", result);

    return 0;
}

// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

Download list_is_set.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/25T1/activities/list_is_set/list_is_set.c .

Your task is to add code to this function in list_is_set.c:

// return 1 if the list is a set
int is_set(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return 42;

}

struct node {
    struct node *next;
    int          data;
};

Add code to is_set so that its returns 1 if the list is a set, and 0 otherwise.

A 'set' is defined as a list that does not repeat an element.

For example if the linked list contains these 8 elements:

16, 7, 8, 12, 13, 19, 21, 12

is_set should return 0, because the element 12 occurs twice.

For example if the linked list contains these 4 elements:

16, 8, 12, 13

Testing

This main function:

• converts the command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls is_set(head)
• prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your is_set function will be called directly in marking. The main function is only to let you test your is_set function

Here is how you use main function allows you to test is_set:

cp -n /import/reed/A/dp1091/public_html/25T1/activities/list_is_set/list_is_set.c .
dcc list_is_set.c -o list_is_set
./list_is_set 16 7 8 12 13 19 21 12
4
./list_is_set 2 4 6 2 4 6
6
./list_is_set 3 5 7 11 13 15 17 19 23 29
0
./list_is_set 2 4 8 16 32 64 128 256
8
./list_is_set
0

Assumptions/Restrictions/Clarifications.

is_set should return a single integer.

is_set should not change the linked list it is given. Your function should not change the next or data fields of list nodes.

is_set should not use arrays.

is_set should not call malloc.

is_set should not call scanf (or getchar or fgets).

You can assume the linked list only contains positive integers.

is_set should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1091 autotest list_is_set

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

struct node {
    struct node *next;
    int          data;
};

int is_set(struct node *head);
struct node *strings_to_list(int len, char *strings[]);

// DO NOT CHANGE THIS MAIN FUNCTION

int main(int argc, char *argv[]) {
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    int result = is_set(head);
    printf("%d\n", result);

    return 0;
}


int count(struct node *head, int n) {

    int count = 0;
    
    while (head != NULL) {

        if (head->data == n) {
            count++;
        }

        head = head->next;
    }

    return count;
}

// return 1 if the list is a set
int is_set(struct node *head) {

    struct node * current = head;
    while (current != NULL) {
        if (count(head, current->data) != 1) {
            return 0;
        }

        current = current->next;
    }

    return 1;

}


// DO NOT CHANGE THIS FUNCTION

// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

Download list_intersection_size.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/25T1/activities/list_intersection_size/list_intersection_size.c .

Your task is to add code to this function in list_intersection_size.c:

// return the number of values which occur in both linked lists
// no value is repeated in either list
int intersection_size(struct node *head1, struct node *head2) {

    // PUT YOUR CODE HERE (change the next line!)
    return 42;

}

struct node {
    struct node *next;
    int          data;
};

Add code to intersection_size so that its returns the number of values that occur in both linked list.

Assume no value occurs more than once in either linked list.

For example, if the two lists contain these values:

3, 1, 4
2, 7, 1, 8, 3

intersection_size should return 2, because these 2 elements occur in both lists:

1, 3

Testing

This main function:

• uses a command line argument of "-" to separate the values for two linked lists.
• converts the command-line arguments before the "-" to a linked list
• assigns a pointer to the first node in the linked list to head1
• converts the command-line arguments after the "-" to a linked list
• assigns a pointer to the first node in the linked list to head2
• calls intersection_size(head1, head2)
• prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your intersection_size function will be called directly in marking. The main function is only to let you test your intersection_size function

Here is how the main function allows you to test intersection_size:

cp -n /import/reed/A/dp1091/public_html/25T1/activities/list_intersection_size/list_intersection_size.c .
dcc list_intersection_size.c -o list_intersection_size
./list_intersection_size 3 1 4 - 2 7 1 8 3
2
./list_intersection_size 16 7 8 12 - 13 19 21 12
1
./list_intersection_size 2 4 6 - 2 4 6
3
./list_intersection_size 3 5 7 11 13 - 15 17 19 23 29
0
./list_intersection_size 1 2 3 4 - 3 2 1
3
./list_intersection_size - 1 2 3 4
0
./list_intersection_size 4 3 2 1 -
0
./list_intersection_size -
0

Assumptions/Restrictions/Clarifications.

No value will occur more than once in either linked list.

intersection_size should not change the linked lists it is given. Your function should not change the next or data fields of list nodes.

intersection_size should not use arrays.

intersection_size should not call malloc.

intersection_size should not call scanf (or getchar or fgets).

intersection_size should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1091 autotest list_intersection_size

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

struct node {
    struct node *next;
    int          data;
};

int intersection_size(struct node *head1, struct node *head2);
int member(int i, struct node *head);
struct node *strings_to_list(int len, char *strings[]);

int main(int argc, char *argv[]) {
    // create two linked lists from command line arguments
    int dash_arg = argc - 1;
    while (dash_arg > 0 && strcmp(argv[dash_arg], "-") != 0) {
        dash_arg = dash_arg - 1;
    }
    struct node *head1 = strings_to_list(dash_arg - 1, &argv[1]);
    struct node *head2 = strings_to_list(argc - dash_arg - 1, &argv[dash_arg + 1]);

    int result = intersection_size(head1, head2);
    printf("%d\n", result);

    return 0;
}

// return the number of values which occur in both linked lists
// no value is repeated in either list
int intersection_size(struct node *head1, struct node *head2) {
    int num_both = 0;
    struct node *p = head1;
    while (p != NULL) {
        if (member(p->data, head2)) {
            num_both = num_both + 1;
        }
        p = p->next;
    }
    return num_both;
}

// return 1 if i occurs in list, 0 otherwise
int member(int i, struct node *head) {
    struct node *p = head;
    while (p != NULL) {
        if (p->data == i) {
            return 1;
        }
        p = p->next;
    }
    return 0;
}


// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

#include <stdio.h>

struct node {
    struct node *next;
    int          data;
};

// return 1 if i  occurs in list, 0 otherwise
int member(int i, struct node *head) {
    if (head == NULL) {
        return 0;
    } if (head->data == i) {
        return 1;
    } else {
        return member(i, head->next);
    }
}

// return the number of values which occur in both linked lists
// no value is repeated in either list
// cute, recursive solution
int intersection_size(struct node *head1, struct node *head2) {
    if (head1 == NULL) {
        return 0;
    } else {
        return member(head1->data, head2) + intersection_size(head1->next, head2);
    }
}

Download list_ordered_insert.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/25T1/activities/list_ordered_insert/list_ordered_insert.c .

Your task is to add code to this function in list_ordered_insert.c:

// ordered_insert should create a new node with the specified value,
// and add it to the list such that the list remains in ascending order.
//
// ordered_insert should return the head of the list.
struct node *ordered_insert(struct node *head, int value) {

    // PUT YOUR CODE HERE (change the next line!)
    return NULL;
}

struct node {
    struct node *next;
    int          data;
};

ordered_insert is given two parameters: a list that is sorted in ascending order (smallest to largest), and a value to insert into the list. ordered_insert should create a new node that contains this value and insert it into the list, such that it remains in ascending order.

ordered_insert should return the head of the list.

Examples

For example, if the list was

1 -> 3 -> 4 -> 5 -> X

ordered_insert should return a pointer to the first node in the list, as this is still the head of the list (the head was not changed).

The list should then look like:

1 -> 2 -> 3 -> 4 -> 5 -> X

X

ordered_insert should return a pointer to the new node that was created, as it is now the head of the list.

The list should then look like:

10 -> X

Testing

list_ordered_insert.c also contains a main function which allows you to test your ordered_insert function.

This main function:

• takes the first command line argument as the value to insert
• converts the remaining command line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls ordered_insert(head)
• prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your ordered_insert function will be called directly in marking. The main function is only to let you test your ordered_insert function

Here is how the main function allows you to test ordered_insert:

dcc list_ordered_insert.c -o list_ordered_insert
./list_ordered_insert 3   4 5
The new list is: [3, 4, 5]
./list_ordered_insert 5   1 3 7 9
The new list is: [1, 3, 5, 7, 9]
./list_ordered_insert 1
The new list is: [1]

Assumptions/Restrictions/Clarifications

You can assume that the provided list is already in order.

You can assume the provided list does not already contain the value you need to insert.

You can assume that the list will only contain positive integers.

You cannot assume anything about number of nodes in the list: there could be no nodes, or there could be very many nodes in the list.

Your submitted file must contain the function: ordered_insert. You may create additional helper functions if you wish.

ordered_insert should return a pointer to the head of the new list.

ordered_insert should not use arrays.

ordered_insert will need to call malloc.

ordered_insert should not call scanf (or getchar or fgets).

ordered_insert should not print anything. It should not call printf.

Do not change the definition of struct node.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1091 autotest list_ordered_insert

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

// DO NOT CHANGE THIS STRUCT
struct node {
    struct node *next;
    int          data;
};

// ordered_insert should create a new node with the specified value,
// and add it to the list such that the list remains in ascending order.
//
// ordered_insert should return the head of the list.
struct node *ordered_insert(struct node *head, int value) {
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = value;
    
    struct node *prev = NULL;
    struct node *curr = head;
    while (curr != NULL && curr->data < value) {
        prev = curr;
        curr = curr->next;
    }
    
    if (prev == NULL) {
        // inserting at head
        new_node->next = head;
        head = new_node;
    } else {
        prev->next = new_node;
        new_node->next = curr;
    }
    
    return head;
}


// If you want, you can write this function to use for debugging.
// It gets called in the main function below.
// If you don't want to write this function, you can just run the
// autotests (which have their own print_list function).
static void print_list(struct node *head) {
    struct node *curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

////////////////////////////////////////////////////////////////////////
//               DO NOT CHANGE THE CODE BELOW                         //
////////////////////////////////////////////////////////////////////////

struct node *ordered_insert(struct node *head, int value);
struct node *strings_to_list(int len, char *strings[]);
static void print_list(struct node *head);


// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Error: you must have at least one argument\n");
        return 1;
    }

    // Grab the first argument to use as the value to insert.
    int to_insert = atoi(argv[1]);

    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 2, &argv[2]);

    // If you're getting an error here,
    // you have returned an uninitialized value
    struct node *new_head = ordered_insert(head, to_insert);
    printf("The new list is: ");
    print_list(new_head);

    return 0;
}

// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

Download list_delete_last.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/25T1/activities/list_delete_last/list_delete_last.c .

Your task is to add code to this function in list_delete_last.c:

//
// Delete the last node in list.
// The deleted node is freed.
// The head of the list is returned.
//
struct node *delete_last(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return NULL;
}

struct node {
    struct node *next;
    int          data;
};

Add code to delete_last so that it deletes the last node from list.

delete_last should return a pointer to the new list.

If the list is now empty delete_last should return NULL.

delete_last should call free to free the memory of the node it deletes.

For example if the linked list contains these 8 elements:

16, 7, 8, 12, 13, 19, 21, 12

delete_last should return a pointer to a list with these elements:

16, 7, 8, 12, 13, 19, 21

Testing

This main function:

• converts the command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls delete_last(head)
• prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your delete_last function will be called directly in marking. The main function is only to let you test your delete_last function

cp -n /import/reed/A/dp1091/public_html/25T1/activities/list_delete_last/list_delete_last.c .
dcc list_delete_last.c -o list_delete_last
./list_delete_last 16 7 8 12 13 19 21 12
[16, 7, 8, 12, 13, 19, 21]
./list_delete_last 2 4 6 2 4 6
[2, 4, 6, 2, 4]
./list_delete_last 42
[]
./list_delete_last
[]

Assumptions/Restrictions/Clarifications.

delete_first should not change the data fields of list nodes.

delete_last should not use arrays.

delete_last should not call malloc.

delete_last should not call scanf (or getchar or fgets).

delete_last should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1091 autotest list_delete_last

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

struct node {
    struct node *next;
    int          data;
};

struct node *delete_last(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
void print_list(struct node *head);

int main(int argc, char *argv[]) {
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    struct node *new_head = delete_last(head);
    print_list(new_head);

    return 0;
}

// Delete the last node in list.
// The deleted node is freed.
// The head of the list is returned.

struct node *delete_last(struct node *head) {
    if (head == NULL) {
        // list is empty no node to delete
        return NULL;
    }
    if (head->next == NULL) {
        // list has one node, head is now NULL
        free(head);
        return NULL;
    }
    struct node *n = head;
    // find second last node in list
    while (n->next->next != NULL) {
        n = n->next;
    }
    free(n->next);
    n->next = NULL;
    return head;
}

// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

// print linked list
void print_list(struct node *head) {
    printf("[");

    for (struct node *n = head; n != NULL; n = n->next) {
        // If you're getting an error here,
        // you have returned an invalid list
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
    }
    printf("]\n");
}

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

struct node {
    struct node *next;
    int          data;
};

// Delete the last node in list - recursive version
// The deleted node is freed.
// The head of the list is returned.

struct node *delete_last(struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    if (head->next == NULL) {
        // list has one node, head is now NULL
        free(head);
        return NULL;
    }
    head->next = delete_last(head->next);
    return head;
}

Download list_delete_second_last.c here

Or, copy these file(s) to your CSE account using the following command:

1091 fetch-activity list_delete_second_last

Your task is to add code to this function in list_delete_second_last.c:

//
// Delete the second last node in the list.
// The deleted node is freed.
// The head of the list is returned.
//
struct node *delete_second_last(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return NULL;
}

Note list_delete_second_last.c uses the following familiar data type:

struct node {
    struct node *next;
    int          data;
};

delete_second_last is given one argument, head, which is the pointer to the first node in a linked list.

Add code to delete_second_last so that it deletes the second last node from list.

delete_second_last should return a pointer to the new list.

If the list is empty, delete_second_last should return NULL.

If the list has exactly one element, delete_second_last should return that one element unchanged.

delete_second_last should call free to free the memory of the node it deletes.

For example if the linked list contains these 8 elements:

16, 7, 8, 12, 13, 19, 21, 12

delete_second_last should return a pointer to a list with these elements:

16, 7, 8, 12, 13, 19, 12

Testing

list_delete_second_last.c also contains a main function which allows you to test your delete_second_last function.

This main function:

• converts the command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls delete_second_last(head)
• prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your delete_second_last function will be called directly in marking. The main function is only to let you test your delete_second_last function

Examples

dcc list_delete_second_last.c -o list_delete_second_last
./list_delete_second_last 16 7 8 12 13 19 21 12
[16, 7, 8, 12, 13, 19, 12]
./list_delete_second_last 2 4 6 2 4 6
[2, 4, 6, 2, 6]
./list_delete_second_last 42
[42]
./list_delete_second_last
[]

Assumptions/Restrictions/Clarifications

• delete_second_last should call free to free the memory for the node it deletes
• delete_second_last should not change the data fields of list nodes.
• delete_second_last should not use arrays.
• delete_second_last should not call malloc.
• delete_second_last should not call scanf (or getchar or fgets).
• delete_second_last should not print anything. It should not call printf.
• Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1091 autotest list_delete_second_last

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

struct node {
    struct node *next;
    int          data;
};

struct node *delete_second_last(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
void print_list(struct node *head);

int main(int argc, char *argv[]) {
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    struct node *new_head = delete_second_last(head);
    print_list(new_head);

    return 0;
}

// Delete the second last node in list.
// The deleted node is freed.
// The head of the list is returned.

struct node *delete_second_last(struct node *head) {
    if (head == NULL || head->next == NULL) {
        // list is empty no node to delete
        return head;
    }
    if (head->next->next == NULL) {
        struct node *tmp = head->next;
        free(head);
        return tmp;
    }
    struct node *n = head;
    // find second last node in list
    while (n->next->next->next != NULL) {
        n = n->next;
    }
    struct node *tmp = n->next;
    n->next = n->next->next;
    free(tmp);

    return head;
}

// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

// print linked list
void print_list(struct node *head) {
    printf("[");

    for (struct node *n = head; n != NULL; n = n->next) {
        // If you're getting an error here,
        // you have returned an invalid list
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
    }
    printf("]\n");
}

Download list_count_last.c here, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1091/public_html/25T1/activities/list_count_last/list_count_last.c .

Your task is to add code to this function in list_count_last.c:

// return the number of values in a linked list equal to the
// last value in that linked list.
int count_last(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return 42;

}

struct node {
    struct node *next;
    int          data;
};

Add code to count_last so that its returns the number of values which are the same as the last value in the list.

For example if the linked list contains these 8 values:

16, 12, 8, 12, 13, 19, 21, 12

count_last should return 3, because 12 is the last value, and 12 occurs 3 times in the list (including the last number).

Testing

This main function:

• converts the command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls count_last(head)
• prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your count_last function will be called directly in marking. The main function is only to let you test your count_last function

Here is how you use main function allows you to test count_last:

cp -n /import/reed/A/dp1091/public_html/25T1/activities/list_count_last/list_count_last.c .
dcc list_count_last.c -o list_count_last
./list_count_last 16 12 8 12 13 19 21 12
3
./list_count_last 2 4 6 2 4 6
2
./list_count_last 3 5 7 11 13 15 17 19 23 29
1
./list_count_last 2 2 2 3 2
4

Assumptions/Restrictions/Clarifications.

count_last will never receive a linked list with no nodes. That is, the head will never be NULL

count_last should return a single integer.

count_last should not change the linked list it is given. Your function should not change the next or data fields of list nodes.

count_last should not use arrays.

count_last should not call malloc.

count_last should not call scanf (or getchar or fgets).

count_last should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1091 autotest list_count_last

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

struct node {
    struct node *next;
    int          data;
};

int count_last(struct node *head);
struct node *strings_to_list(int len, char *strings[]);

// DO NOT CHANGE THIS MAIN FUNCTION

int main(int argc, char *argv[]) {
    // create linked list from command line arguments
    struct node *head = strings_to_list(argc - 1, &argv[1]);

    int result = count_last(head);
    printf("%d\n", result);

    return 0;
}


// return the number of values in a linked list equal to the
// last value in that linked list.
int count_last(struct node *head) {
    int last_val;
    struct node *iter = head;
    while (iter) {
        last_val = iter->data;
        iter = iter->next;
    }

    int count = 0;
    iter = head;
    while (iter) {
        if (iter->data == last_val) count++;
        iter = iter->next;
    }

    return count;

}


// DO NOT CHANGE THIS FUNCTION

// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    for (int i = len - 1; i >= 0; i = i - 1) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
    }
    return head;
}

Download list_delete_range.c here

Or, copy these file(s) to your CSE account using the following command:

1091 fetch-activity list_delete_range

Your task is to add code to this function in list_delete_range.c:

//
// Given the head of a linked list, deletes all nodes in range `start` to `end`.
// Nodes can be identified by an "index", of which the first node has index 0.
//
// Returns the head of the list afterwards.
//
struct node *delete_range(struct node *head, int start, int end) {
    // TODO: COMPLETE THIS FUNCTION AND CHANGE THIS RETURN
    return NULL;
}

In this exercise, every node in the linked list provided can be thought of as having a "place" in the list. For example, the first node will be at place "1", the second at place "2" and so on. You will be given both a start/end position in which all nodes inbetween (inclusive) are to be deleted.

Examples

dcc list_delete_range.c -o list_delete_range
./list_delete_range
Total numbers: 6
6 5 4 3 2 1
Enter delete range: 2 4
List before: [6, 5, 4, 3, 2, 1]
List after: [6, 5, 1]
./list_delete_range
Total numbers: 10
5 1 10 -1 3 6 -5 3 40 1
Enter delete range: 3 8
List before: [5, 1, 10, -1, 3, 6, -5, 3, 40, 1]
List after: [5, 1, 10, 1]
./list_delete_range
Total numbers: 5
1 2 3 4 5
Enter delete range: 0 2
List before: [1, 2, 3, 4, 5]
List after: [4, 5]
./list_delete_range
Total numbers: 5
1 2 3 4 5
Enter delete range: 0 10
List before: [1, 2, 3, 4, 5]
List after: []

Assumptions/Restrictions/Clarifications

• You will always be given integer inputs
• When considering the each node in the range, their positioning starts at 0
• The range components will always be given such that start < end
• All range components will be non-negative
• The "end" given can be larger than the length of the list
• The entire delete range can be outside of the list. E.g. if a list has 3 nodes, the delete range can still be 10 to 15.

When you think your program is working you can use autotest to run some simple automated tests:

1091 autotest list_delete_range

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

#define FALSE 0
#define TRUE 1

#define MAX_LIST_LEN 100

struct node {
    struct node *next;
    int          data;
};

struct node *delete_range(struct node *head, int start, int end);
struct node *array_to_list(int len, int array[]);
void print_list(struct node *head);
void free_list(struct node *head);

// DO NOT CHANGE THIS MAIN FUNCTION

int main(void) {
    // get list size
    int list_size;
    printf("Total numbers: ");
    scanf(" %d", &list_size);

    // read in numbers
    int list[MAX_LIST_LEN] = {0};
    int index_count = 0;
    while (index_count < list_size && scanf(" %d", &list[index_count])) {
        index_count++;
    }

    if (index_count < list_size) {
        printf("You must enter numbers equal to the total provided.\n");
        return 1;
    }

    // create linked list from input numbers
    struct node *head = NULL;
    if (index_count > 0) {
        // list has elements
        head = array_to_list(list_size, list);
    }

    int range_start;
    int range_end;
    printf("Enter delete range: ");
    if (scanf("%d %d", &range_start, &range_end) != 2) {
        printf("You must enter both a start and an end for the range.\n");
        return 2;
    }
    
    printf("List before: ");
    print_list(head);
    struct node *new_head = delete_range(head, range_start, range_end);
    printf("List after: ");
    print_list(new_head);
    free_list(new_head);

    return 0;
}


//
// Given the head of a linked list, deletes all nodes in range `start` to `end`.
// Nodes can be identified by an "index", of which the first node has index 0.
//
// Returns the head of the list afterwards.
//
struct node *delete_range(struct node *head, int start, int end) {
    // `start` should always be less than `end` in a range.
    if (start > end) {
        return head;
    }

    // Keep track of the nodes before and after deletion range.
    struct node *before_range = NULL;
    struct node *after_range = NULL;

    // Flag for whether we are currently in the deletion range
    int in_deletion_range = FALSE;

    int node_count = 0;

    struct node *previous = NULL;
    struct node *current = head;

    while (current != NULL) {
        if (node_count == start) {
            before_range = previous;
            in_deletion_range = TRUE;
        }
        if (node_count == end + 1) {
            after_range = current;
            in_deletion_range = FALSE;
        }

        previous = current;
        current = current->next;
        if (in_deletion_range == TRUE) {
            // Update the head if it were to be deleted, for ease of use later.
            if (previous == head) {
                head = NULL;
            }
            free(previous);
        }

        node_count++;
    }

    // In this case, we either never entered the range or the entire list was
    // in the range.
    if (before_range == NULL && after_range == NULL) {
        return head;
    }
    // This indicates that the head was in range and thus removed. As a result,
    // `after_range` is the new head.
    if (before_range == NULL) {
        return after_range;
    // Otherwise, we link up the two nodes at the boundaries to get our new
    // list.
    } else {
        before_range->next = after_range;
        return head;
    }
}


// DO NOT CHANGE THIS FUNCTION
// create linked list from array of ints
struct node *array_to_list(int len, int array[]) {
    struct node *head = NULL;
    int i = len - 1;
    while (i >= 0) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = array[i];
        head = n;

        i--;
    }

    return head;
}

// DO NOT CHANGE THIS FUNCTION
// print linked list
void print_list(struct node *head) {
    printf("[");

    for (struct node *n = head; n != NULL; n = n->next) {
        // If you're getting an error here,
        // you have returned an invalid list
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
    }
    printf("]\n");
}

// DO NOT CHANGE THIS FUNCTION
// free linked list
void free_list(struct node *head) {
    if (head != NULL) {
        free_list(head->next);
        free(head);
    }
}

Download list_join_detection.c here

Or, copy these file(s) to your CSE account using the following command:

1091 fetch-activity list_join_detection

Your task is to add code to these functions in list_join_detection.c:

//
// Gets the index relative to `second_list` where `first_list` and
// `second_list` join together.
//
// Returns this index if found, otherwise return -1
//
int join_detection_point(struct node *first_list, struct node *second_list) {
    // TODO: Implement this function (And delete the line below)
    return -1;
}

In this exercise you will scan in values for two different lists and will be asked where to join the second list to the first list.

Here is an example:

dcc list_join_detection.c -o list_join_detection
./list_join_detection
Enter first list: 1 2 3 4 5
Enter second list: 6 7 8 9
Which node of list 1 will the end of list 2 point at? 2
These lists join at node 4 of the second list!

In this example we have two lists first_list and second_list. However, the end of second_list is pointing into first_list. This is what we're interested in and is what we specify in the third line of input. When 2 was input, the end of the second list will point at node 2 of the first list (we are counting the first node as node 0).

The last line of output is what your function will be implementing. That is, the first node in the second_list that also exists in the first_list.

Please note that looking at the input should make it very obvious when this occurs as you know what the second list looks like. However, inside the function you will not have this luxury, as all the pointers have been setup for both lists.

As a result, you are given the final versions of both lists and need to determine where they join.

Examples

dcc list_join_detection.c -o list_join_detection
./list_join_detection
Enter first list: 1 6 -10 4 3 50 20 6
Enter second list: 0 0 5 4 1 -10 3 4 6 9 10 3 6 20
Which node of list 1 will the end of list 2 point at? 5
These lists join at node 14 of the second list!
./list_join_detection
Enter first list: 0 5 2 10
Enter second list: 1 3
Which node of list 1 will the end of list 2 point at? 7
These lists do not join at all.

Assumptions/Restrictions/Clarifications

• You will always be provided valid input
• Providing any index for first_list that does not exist means that second_list will never point into it
• You should return -1 if the two lists do not join
• You cannot use the values of nodes to determine if they are in both lists. This because two nodes can have the same value. How could you check if both lists point at the same node at a certain point?

When you think your program is working you can use autotest to run some simple automated tests:

1091 autotest list_join_detection

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

#define MAX_INPUT_STRING_LENGTH 1024

struct node {
    struct node *next;
    int          data;
};

int join_detection_point(struct node *first_list, struct node *second_list);
struct node *scan_in_list();
struct node *string_to_list(char *string);

// DO NOT CHANGE THIS MAIN FUNCTION

int main(void) {
    printf("Enter first list: ");
    struct node *first_list = scan_in_list();
    printf("Enter second list: ");
    struct node *second_list = scan_in_list();
    if (second_list == NULL) {
        printf("The second list will always have at least 1 element.\n");
        return 1;
    }

    printf("Which node of list 1 will the end of list 2 point at? ");
    int node_index;
    scanf("%d", &node_index);

    // Find the node we need the end of the second list to point at.
    struct node *current_node = first_list;
    int counter = 0;
    while (current_node != NULL && counter != node_index) {
        current_node = current_node->next;
        counter++;
    }

    // Find the last node of the second list to join them together
    struct node *last_node = second_list;
    while (last_node->next != NULL) {
        last_node = last_node->next;
    }

    last_node->next = current_node;

    int res = join_detection_point(first_list, second_list);
    if (res == -1) {
        printf("These lists do not join at all.\n");
    } else {
        printf("These lists join at node %d of the second list!\n", res);
    }

    return 0;
}

//
// Gets the index relative to `second_list` where `first_list` and
// `second_list` share a node.
//
// Returns this index if found, otherwise return -1
//
int join_detection_point(struct node *first_list, struct node *second_list) {
    int point = -1;

    struct node *second_list_curr = second_list;
    int second_list_index = 0;
    while (second_list_curr != NULL && point == -1) {
        struct node *first_list_curr = first_list;
        while (first_list_curr != NULL && point == -1) {
            // Compare the addresses of every pair of nodes in list 1 and 2.
            // The first time they are equal is the point where the lists
            // joined.
            if (first_list_curr == second_list_curr) {
                point = second_list_index;
            }
            first_list_curr = first_list_curr->next;
        }

        second_list_curr = second_list_curr->next;
        second_list_index++;
    }

    return point;
}

// DO NOT CHANGE THIS FUNCTION
// Handles input/output to scan in a list
struct node *scan_in_list() {
    char inputs[MAX_INPUT_STRING_LENGTH];
    char *input_res = fgets(inputs, MAX_INPUT_STRING_LENGTH, stdin);

    // create linked list input line
    struct node *head = NULL;
    if (input_res != NULL) {
        // Remove newline off string
        if (inputs[strlen(inputs) - 1] == '\n') {
            inputs[strlen(inputs) - 1] = '\0';
        }
        
        // Make sure all elements are valid
        int i = 0;
        // Flag for whether string is valid. An empty string is not valid and
        // initial value is based off that.
        int valid_string = strlen(inputs) > 0;
        while (valid_string && inputs[i] != '\0') {
            // Strings can only contain numbers/spaces
            if ((inputs[i] < '0' || inputs[i] > '9') && inputs[i] != ' ' && inputs[i] != '-') {
                printf("%c\n", inputs[i]);
                valid_string = 0;
            }
            i++;
        }
        
        if (valid_string) {
            head = string_to_list(inputs);
        }
    }

    return head;
}

// DO NOT CHANGE THIS FUNCTION
// create linked list from string of ints
struct node *string_to_list(char *string) {
    struct node *head = NULL;
    struct node *tail = NULL;

    char *token = strtok(string, " ");

    while (token != NULL) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = NULL;
        n->data = atoi(token);
        if (head == NULL) {
            head = n;
            tail = n;
        } else {
            tail->next = n;
            tail = n;
        }

        token = strtok(NULL, " ");
    }   

    return head;
}