# Exercises

# 13.5. Exercises#

Many of these exercises are taken from past exams of APS105 Computer Fundamentals courses at University of Toronto. The solutions are provided in the answer boxes.

Headings in this page classify the exercises into different categories: **[Easy]**, **[Intermediate]**, and **[Challenging]**. I suggest you start by easy exercises and work your way up to the challenging ones.

**Question 5 in Winter 2018 Final Exam [Easy]**

Complete the following C program, designed to search for an int-type item, called `key`

, in a linked list, pointed to by `head`

.

```
typedef struct node {
int data;
struct node *link;
} Node;
Node *search(Node *head, int key) {
Node *current = head;
// insert your code in the line below between the parentheses
while ( ) {
current = current->link;
}
return current;
}
```

Answer

```
1typedef struct node {
2 int data;
3 struct node *link;
4} Node;
5
6Node *search(Node *head, int key) {
7 Node *current = head;
8
9 while (current != NULL && current->data != key) {
10 current = current->link;
11 }
12
13 return current;
14}
```

**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;
}
```

Answer

```
Node *predecessor(Node *head, Node *searchNode) {
Node *current;
current = head;
if (head == searchNode) {
return NULL;
}
while (current != NULL) {
if (current->link == searchNode) {
return current;
}
// write your 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
}
```

Answer

```
void printDuplicates(Node *head) {
Node *current = head;
while (current != NULL) {
Node *runner = current->next;
while (runner != NULL) {
if (current->data == runner->data) {
printf("%d\n", current->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

Answer

```
void simplify(Node *head) {
Node *current;
current = head;
if (current == NULL) {
return;
}
while (current->link != 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
}
```

Answer

```
Node *newNode(int newValue, Node *link) {
Node *newNode;
Node *node = (Node *)malloc(sizeof(Node));
if (node != NULL) {
node->data = newValue;
node->next = link;
}
return node;
}
Node *buildJoinedList(Node *firstList, Node *secondList) {
Node *current = secondList, *head = NULL, *tail = NULL;
while (current != NULL) {
if (head == NULL) {
head = newNode(current->data, NULL);
tail = head;
current = current->next;
} else {
tail->next = newNode(current->data, NULL);
tail = tail->next;
current = current->next;
}
}
current = firstList;
while (current != NULL) {
if (head == NULL) {
head = newNode(current->data, NULL);
tail = head;
current = current->next;
} else {
tail->next = newNode(current->data, NULL);
tail = tail->next;
current = current->next;
}
}
return head;
}
```

**Question 14 in Winter 2022 Final Exam [Challenging]**

The `Node`

structure in a linked list has been defined as follows:

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

The `LinkedList`

structure has also been defined to contain the `head`

of a linked list:

```
typedef struct linkedList {
Node *head;
} LinkedList;
```

Write a C function called `reorder`

, the prototype of which is given below, that reorders the nodes in a linked list such that nodes with a value of \(0\) appear at the **front** of the linked list and nodes with any other integer value appear at the end of the linked list, while maintaining the original order of non-zero nodes.

**Example 1:**

Input List: 0 0 15 0 0 13 10 Output List: 0 0 0 0 15 13 10

**Example 2:**

Input List: 1 0 19 0 0 5 0 Output List: 0 0 0 0 1 19 5

**Note:** You are not allowed to copy or modify the `data`

member in any of the nodes in the linked list. However, you can modify the `next`

pointer in the nodes.

Answer

**Solution 1:**

```
void reorder(LinkedList *list) {
Node *tail = list->head, *prev = NULL, *curr = list->head;
while (tail->next != NULL) // Find the tail of the list
tail = tail->next;
Node *newTail = tail;
while (curr->data != 0 && curr != tail) {
newTail->next = curr;
curr = curr->next;
newTail->next->next = NULL;
newTail = newTail->next;
}
if (curr->data == 0) {
list->head = curr; // Make head to point to first 0
while (curr != tail) {
if (curr->data == 0) {
prev = curr;
curr = curr->next;
} else {
prev->next = curr->next;
curr->next = NULL;
newTail->next = curr;
newTail = curr;
curr = prev->next;
}
}
} else {
prev = curr;
}
// check if more 0 nodes and end is non-zero
if (newTail != tail && tail->data != 0) {
prev->next = tail->next;
tail->next = NULL;
newTail->next = tail;
}
}
```

**Solution 2:**

```
void reorderAlternative(LinkedList *list) {
Node *current = list->head;
Node *prev = NULL;
while (current != NULL) {
if (current->data == 0) { // insert at front of list
if (current == list->head) {
// traverse and do nothing
prev = current;
current = current->next;
} else { // order is very important
Node *temp = current;
prev->next = current->next; // prev should be as is
current = current->next;
temp->next = list->head;
list->head = temp;
}
} else {
// traverse and do nothing
prev = current;
current = current->next;
}
}
}
```