Coding Interview Practice: Linked Lists

linkedlist.c

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

struct Node
{
    int value;
    struct Node *next;
};

struct List 
{
    struct Node *head;
};

struct List *
list_new()
{
    struct List *list = calloc(sizeof(struct List), 1);
    assert(list);
    return list;
}

struct Node *
node_new(int value)
{
    struct Node *node = calloc(sizeof(struct Node), 1);
    assert(node);
    node->value = value;
    return node;
}

void
list_append(struct List *list, int value)
{
    assert(list);
    struct Node *node = node_new(value);
    assert(node);
    if (!list->head)
    {
        list->head = node;
    }
    else
    {
        struct Node *current = list->head;
        for (; current->next != NULL; current = current->next);
        current->next = node;
    }
}

void
list_delete(struct List *list) 
{
    assert(list);
    struct Node *current = list->head;
    while (current)
    {
        struct Node *tmp = current;
        current = current->next;
        free(tmp);
    }
    free(list);
}

int
list_remove(struct List *list, int value) 
{
    assert(list);
    if (!list->head) 
        return 0; /* empty list */
    if (list->head->value == value) 
    {
        list->head = list->head->next;
        return 1;
    }
    else
    {
        struct Node *current = list->head->next;
        struct Node *prev = list->head;
        while (current) 
        {
            if (current->value == value)
            {
                prev->next = current->next;
                free(current);
                return 1;
            }
            current = current->next;
        }
        return 0;
    }
}

int
remove_third_last(struct List *list) 
{
    assert(list);
    struct Node *lead = list->head, *follow = list->head, *prev = NULL;
    int i;
    for (i = 0; i < 3 && lead; ++i)
        lead = lead->next;
    if (i != 3)
        return 0; /* list is shorter than 3 elements */
    while (lead)  /* go forward until lead reaches the end of the list */
    {
        lead = lead->next;
        prev = follow;
        follow = follow->next;
    } /* follow now points at the element we want to delete */
    if (follow == list->head)
        list->head = follow->next;
    else
        prev->next = follow->next;
    free(follow);
    return 1;
}

int
detect_loop(struct List *list) 
{
    assert(list);
    struct Node *fast = list->head, *slow = list->head;
    if (fast)
        fast = fast->next;
    else
        return 0; /* empty list */
    while (fast && slow) 
    {
        if (fast == slow)
            return 1; /* loop detected */
        fast = fast->next;
        if (!fast)
            break;
        else
            fast = fast->next;
        slow = slow->next;
    }
    return 0;
}

void
merge_sort_helper(struct Node **head)
{
    if (*head == NULL)
        return; /* empty list */

    /* break list into left and right sublists */
    struct Node *fast = (*head)->next;
    struct Node *slow = *head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    struct Node *left = *head;
    struct Node *right = slow->next;
    if (!right)
        return; /* list of size 1 */
    slow->next = NULL;

    /* recursive step */
    merge_sort_helper(&left);
    merge_sort_helper(&right);

    /* merge step */
    struct Node *new_head = NULL;
    struct Node *tail = NULL;
    for (;;)
    {
        /* determine next element to merge in, if any are left */
        struct Node *next = NULL;
        if (left && right)
            next = left->value < right->value ? left : right;
        else if (left)
            next = left;
        else if (right)
            next = right;
        else
            break;
        assert(next);

        /* append to linked list */
        if (new_head)
            tail->next = next;
        else
            new_head = next;

        /* advance pointers */
        if (next == left)
            left = left->next;
        else
            right = right->next;

        tail = next;
        tail->next = NULL;
    }
    *head = new_head;
}

/* in-place merge sort of the list */
void
merge_sort(struct List *list)
{
    merge_sort_helper(&list->head);
}

void
remove_duplicates(struct List *list)
{
    assert(list);
    merge_sort(list);
    struct Node *current = list->head;
    struct Node *prev = NULL;
    while (current)
    {
        if (prev && prev->value == current->value)
        {
            prev->next = current->next;
            free(current);
        }
        prev = current;
        current = current->next;
    }
}

void 
print_list(struct List *list)
{
    assert(list);
    struct Node *current = list->head;
    printf("[");
    for (; current; current = current->next)
        printf("%d, ", current->value);
    printf("]\n");
}

int
main(void)
{
    struct List *list = list_new();
    int i;
    for (i = 0; i < 10; ++i)
        list_append(list, i);
    print_list(list);
    remove_third_last(list);
    print_list(list);
    printf("detect_loop: %d\n", detect_loop(list));
    list->head->next->next->next = list->head;
    printf("detect_loop: %d\n", detect_loop(list));
    /* there's a loop in that list so we can't reliably delete it... */
    //list_delete(list);

    list = list_new();
    for (i = 0; i < 10; ++i)
        list_append(list, 10-i);
    print_list(list);
    merge_sort(list);
    print_list(list);
    list_delete(list);

    list = list_new();
    for (i = 0; i < 10; ++i)
    {
        list_append(list, 10-i);
        list_append(list, i);
    }
    print_list(list);
    remove_duplicates(list);
    print_list(list);
    return 0;
}

Makefile

CFLAGS=-ggdb -Wall

all: linkedlist.out

# $< the dependencies
# $@ the target
linkedlist.out: linkedlist.o
	gcc -Wall -ggdb $< -o $@

clean:
	rm -rf *.out *.o