Linked list for interview

linkedlist.c

// linkedlist.c : Defines the entry point for the console application.
//

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

typedef struct node {
	int val;
	struct node * next;
} node_t;


/**
 * Create a node with the given value.
 * The value must be greater than 0.
 * @input (int) val: the value for new node.
 * @return (node *): a pointer to the new node. 
 *
 **/
node_t * createNode(int val) {
	node_t * current = NULL;
	if (val < 0) {
		return NULL;
	}
	current = malloc(sizeof(node_t));
	if (current == NULL) {
		return NULL;
	}
	current->val = val;
	current->next = NULL;
	return current;
}


/**
 * Add a value to the end of the linked list.
 * @input (node_t *) head: a pointer to the head of the linked list.
 * @input (int) val: the value to add.
 *
 **/
void addLast(node_t * head, int val) {
	node_t * current = head;
	while (current->next != NULL) {
		current = current->next;
	}

	current->next = createNode(val);
}

/**
* Add a value to the beginning of the linked list.
* If the list is empty, return a new list.
* @input (node_t **) head: a double pointer to the head of the linked list.
* @input (int) val: the value to add.
*
**/
void addFirst(node_t ** head, int val) {
	node_t * newNode;
	newNode = createNode(val);
	newNode->next = *head;
	*head = newNode;
}

/**
 * Remove the first node in the linked list.
 * If the list is empty, return -1.
 * @input (node_t **) head: a double pointer to the head of the linked list.
 * @return (int): the value of the removed node.
 *
 **/
int removeFirst(node_t **head) {
	int val = -1;
	node_t * next = NULL;

	if (*head == NULL) {
		return val;
	}

	next = (*head)->next;
	val = (*head)->val;
	free(*head);
	*head = next;

	return val;
}

/**
 * Remove the last node in the linked list.
 * If the list is empty, return -1.
 * @input (node_t *) head: a pointer to the head of the linked list.
 * @return (int): the value of the removed node.
 *
 **/
int removeLast(node_t *head) {
	int val = -1;
	node_t * previous = NULL;
	
	if (head == NULL) {
		return val;
	}

	while (head->next != NULL) {
		previous = head;
		head = head->next;
	}

	val = head->val;
	free(head);

	if (previous) {
		previous->next = NULL;
	}

	return val;
}

/** 
 * Returns the length of the list.
 * @input (node_t *) head: a pointer to the head of the linked list.
 * @return (int): the length of the list.
 *
 **/
int length(node_t *head) {
	int size = 0;
	while (head != NULL) {
		head = head->next;
		size++;
	}
	return size;
}

/**
* Determines if there is a loop in the linked list.
* @input (node_t *) head: a pointer to the head of the linked list.
* @return (int): 1 if true, 0 if false
*
**/
int isLoop(node_t *head) {
	return 0;
}

/**
 * Determines if two linked lists intersect.
 * Returns the address of the node. 
 * If there is no intersection, return NULL.
 * @input (node_t *) head1: a pointer to the head of the first linked list.
 * @input (node_t *) head2: a pointer to the head of the second linked list.
 * @return (node_t *): Address of intersection if it exists, else NULL.
 *
 */
node_t * isIntersecting(node_t *head1, node_t *head2) {
	return NULL;
}


int main()
{
	node_t * head = createNode(5);

	printf("Created one node\n");
	assert(length(head) == 1);

	printf("Added node to beginning\n");
	addFirst(&head, 4);
	assert(length(head) == 2);
	assert(head->val == 4);
	assert(head->next->val == 5);

	printf("Added node to end\n");
	addLast(head, 6);
	assert(length(head) == 3);
	assert(head->val == 4);
	assert(head->next->next->val == 6);

	printf("Removing beginning node\n");
	assert(removeFirst(&head) == 4);
	assert(length(head) == 2);

	printf("Removing last node\n");
	assert(removeLast(head) == 6);
	assert(length(head) == 1);

	printf("Remove first node\n");
	assert(removeFirst(&head) == 5);
	assert(length(head) == 0);

	printf("Remove last node of empty list\n");
	assert(removeLast(head) == -1);
	assert(length(head) == 0);
	
	printf("Remove first node of empty list\n");
	assert(removeFirst(&head) == -1);
	assert(length(head) == 0);



	printf("All correct!\n");
	
  return 0;
}

questions.txt

What are dangling pointers and memory leaks? Why are they bad? 



isLoop
	Best Solution: (Floyd’s Cycle-Finding Algorithm)
		Increment one pointer by 1, the other by 2. If the two pointers are equal, then you must have a loop.
	Worse solutions:
		Hash each node, check hashes.
		Modify node class, add a visited flag.
		
isIntersecting
	Best Solution:
		Find the difference of the length in the lists. (d)
		Traverse the bigger list d times, so that the length of the two lists are even.
		Then traverse each list, checking if the pointers are the same.
		Return the pointer.
	Worse solutions:
		For every node in L1, check if it exists in L2
		For every node in L1, hash it. For every node in L2, check if hash exists.