Question 6 in Winter 2016 Final Exam (Easy)

Consider the following code, where head points to the head of a linked list:

typedef struct node {
  int value;
  struct node *link;
} Node;

Node *head;

Complete the following C function that returns a pointer to the node that precedes (comes before) searchNode, if it is found in the linked list. If searchNode is not found or the linked list is empty, the function should return NULL. Read the function carefully: you may need to add code in several locations.

Node *predecessor(Node *head, Node *searchNode) {
  Node *current;
  current = head;
  if (head == searchNode) return NULL;
  // COMPLETE THE NEXT LINE:
  while (                                          ) {
    if (current->link == searchNode) return current;
    // WRITE CODE HERE:
  }
  return NULL;
}

My solution

Node *predecessor(Node *head, Node *searchNode) {
  Node *current;
  current = head;
  if (head == searchNode) {
	  return NULL;
  }
  // COMPLETE THE NEXT LINE:
  while (current != NULL) {
    if (current->link == searchNode) {
	    return current;
    }
    // WRITE CODE HERE:
    current = current->link;
  }
  return NULL;
}

Question 13 in Winter 2018 Final Exam (Intermediate)

The following C structure is used to define each node in a linked list:

typedef struct node {
  int data;
  struct node *link;
} Node;

Write a C function called printDuplicates that receives a pointer to the first node (head) of a linked list as a parameter. The function should find and print the duplicate integers in the linked list. For example, if the linked list contains the integers 6, 3, 3, 6, 7, 4, then the printDuplicates() function should print:

6
3

Note: In your solution, you may assume that a given integer occurs at most twice in the linked list.

void printDuplicates(Node *head) {
    // insert your code here
}

My solution

void printDuplicates(Node *head) {
	// insert your code here
	Node *current = head;
	while (current != NULL) {
		Node *runner = current->link;
		while (runner != NULL) {
			if (runner->data == current->data) {
				printf("%d\n", runner->data);
			}
			runner = runner->next;
		}
		current = current->next;
	}
}

Question 12 in Winter 2016 Final Exam (Intermediate)

The following C structure is used to define each node in a linked list:

typedef struct node {
  int value;
  struct node* link;
} Node;

Assume that nodes in the linked list are maintained in order of their values, such that the value stored in each node is greater than or equal to the value in predecessor nodes. Write a C function:

void simplify(Node *head)

that deletes any duplicate items in the linked list. The parameter head is a pointer to the head node of a linked list. Note that the head node of the linked list will remain unchanged after the deletions are made. For example, if before calling simplify, the linked list contains:

13 13 15 15 17 17 17 19 22 25 25 28

then after calling the function, the list should contain:

13 15 17 19 22 25 28

My solution

void simplify(Node *head) {
	Node *current = head;
	if (current == NULL) {
		return;
	}
	while (current != NULL) {
		if (current->value == current->link->value) {
			Node *nodeToRemove = current->link;
			current->link = current->link->link;
			free(nodeToRemove);
		} else {
			current = current->link;
		}
	}
}

Question 14 in Winter 2017 Final Exam (Challenging)

The following C structure is used to define each node in a linked list:

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

Write a C function, called buildJoinedList, that takes two linked lists called firstList and secondList as its parameters, and returns a new list that joins the two lists, with secondList at the front. Both firstList and secondList are pointers to the first node of a linked list. The function should return a pointer to a new list that is dynamically allocated.

Note that the existing linked lists pointed to by firstList and secondList must not be modified in any way.

An example of how the function should work is as follows: if firstList points to a linked list containing nodes storing the numbers $1,2,3,4,5$ and secondList containing the numbers $6,7,8,9,10$, then the newly created list returned by the buildJoinedList function should contain nodes storing the numbers $6,7,8,9,10,1,2,3,4,5$.

Node *buildJoinedList(Node *firstList, Node *secondList) {
    // insert your code here
}

My solution

Node *createNewNode(int value, Node *link) {
  // creates a new node
  Node *newNode = (Node *)malloc(sizeof(Node));
  if (newNode != NULL) {
	  newNode->data = value;
	  newNode->next = link;
  }
  return newNode;
}

Node *buildJoinedList(Node *firstList, Node *secondList) {
  Node *current = secondList;
  Node *newListHead = (Node *)malloc(sizeof(Node));
  Node *newListCurrent = newListHead;
  while (current != NULL) {
    Node *newListNode = createNewNode(current->data, NULL);
    newListCurrent->next = newListNode;
    current = current->next;
    newListCurrent = newListCurrent->next;
  }
  current = firstList;
  while (current != NULL) {
    Node *newListNode = createNewNode(current->data, NULL);
    newListCurrent->next = newListNode;
    current = current->next;
    newListCurrent = newListCurrent->next;
  }
  return newListHead;
}

Note: I don't know if this is right, but I'm too lazy to check right now.