Week 09 Extra Sample Solutions

#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);
    }
}

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

struct node {
    struct node *left;
    struct node *right;
    char         data;
};

void print_list(struct node *head);
struct node *scan_in_list();

// DO NOT CHANGE THIS MAIN FUNCTION

int main(void) {
    printf("Enter list: ");
    struct node *head = scan_in_list();
    print_list(head);
    return 0;
}

// Given the `head` of a list, prints the string it contains as well as the
// numbers of lefts/rights taken.
void print_list(struct node *head) {
    struct node *current = head;

    int left_count = 0;
    int right_count = 0;
    
    printf("List string:   ");
    while (current != NULL) {
        printf("%c", current->data);

        // Traverse either left or right based on where the next node would be.
        // Since left/right counts need to be accounted for, both the left and
        // right pointers need to be checked more explicitly.
        if (current->left == NULL && current->right == NULL) {
            current = NULL;
        } else if (current->left == NULL) {
            current = current->right;
            right_count++;
        } else {
            current = current->left;
            left_count++;
        }
    }

    printf("\n");
    printf("#Lefts Taken:  %d\n", left_count);
    printf("#Rights Taken: %d\n", right_count);
}

// Malloc's a new node given `left`, `right`, `data` values. Returns this node.
struct node *create_node(struct node *left, struct node *right, char data) {
    struct node *new = malloc(sizeof(struct node));
    new->left = left;
    new->right = right;
    new->data = data;

    return new;
}

// DO NOT CHANGE THIS FUNCTION
// Handles input/output to scan in a list
struct node *scan_in_list() {
    char data;
    char direction;

    // Head of list is NULL if no initial data is given.
    if (scanf(" %c", &data) != 1) {
        return NULL;
    }

    struct node *head = create_node(NULL, NULL, data);

    struct node *previous_node = head;
    // Loop through for every (direction, data) pair and linked up list
    while (scanf(" %c %c", &direction, &data) == 2) {
        assert(direction == 'L' || direction == 'R');

        struct node *new = create_node(NULL, NULL, data);
        if (direction == 'L') {
            previous_node->left = new;
            previous_node = previous_node->left;
        } else {
            previous_node->right = new;
            previous_node = previous_node->right;
        }
    }

    return head;
}