*907*

Question: Given a Linked List, we need to find the middle of the list and print the number.

Input: 4, 8, 15, 16, 23, 42, 99

Output: 16

This is a very basic question and is a part of a bigger problem. However, there are several approaches to solve the above problem.

#### BRUTE-FORCE APPROACH

In this approach, we count the number of nodes in the list for each of the node and see whether it is the middle.

struct node * bruteForce(struct node * head) { // making 2 temporary variables struct node * temp1 = head; struct node * temp2 = head; // index for current node int index = 1; while(temp2 != NULL) { // to count the number of nodes int count = 0; // counting nodes for each node temp 1 = head; while(temp1 != NULL) { count++; temp1 = temp1 -> next; } // the terminating condition if(index == (count/2)) break; index++; temp2 = temp2 -> next; } // the temp2 points to the middle return temp2; }

*Time Complexity:* O(n^{2})

*Space Complexity:* O(1)

#### MORE SIMPLIFIED APPROACH

In this approach, we will scan the entire list and count the number of nodes. We divide the number by 2 and then again traverse the list up-to that node.

struct node * middleInTwoScans(struct node * head) { struct node * temp = head; // counting the number of nodes int count = 0; while(temp != NULL) { count++; temp = temp -> next; } // to get the middle node count count = count/2; // returning to first position temp = head; // traversing for n/2 times while(count--) temp = temp -> next; // temp points at middle node return temp; }

*Time Complexity: *Time for finding the length + Time for locating middle node = O(n) + O(n) ≈ O(n)

*Space Complexity:* O(1)

#### USING HASH TABLE

What we can do is create a hash table and store the index of all the nodes in the List. Then to get the middle node, we can directly point to the node (n/2), where n is the size of the Linked List.

struct node * hashTableMiddle(struct node * head) { struct node * temp = head; int count = 0; while(temp) { count++; temp = temp -> next; } // using array to create hash table struct node * arr = (struct node *)malloc(sizeof(struct node)*count); temp = head; count = 0; while(temp) { arr[count] = temp -> data; count++; temp = temp -> next; } return arr[(count/2)]; }

*Time Complexity:* O(n)

*Space Complexity:* O(n)

#### USING ONLY ONE SCAN – THE MOST EFFICIENT WAY

We can solve this problem using only one scan on the Linked List. The approach lies in a simple trick of using two pointers to traverse the list.

- ptr1 travels one node at a time
- ptr2 travels two nodes a time.

Thus, when ptr2 reaches the end of the Linked List, ptr1 will point at the middle of the Linked List.

// implementing a function that returns the middle of a Linked List struct node * findMiddleOfLinkedList(struct node * head) { // a pointer that travels one node a time struct node * slowPtr = head; // a pointer that travels two nodes at a time struct node * fastPtr = head; while(fastPtr -> next != NULL) { // the slow Ptr moves one step slowPtr = slowPtr -> next; // the fast Ptr moves two steps fastPtr = fastPtr -> next; if(fastPtr == NULL) break; fastPtr = fastPtr -> next; if(fastPtr == NULL) break; } // the slow Ptr now points at the middle of the Linked List return slowPtr; }

*Time Complexity:* O(n)

*Space Complexity:* O(1)

You can download the working sample of the code here implementing the last method. Open it using any of your favorite editor (gEdit, Notepad++, wordpad etc…)