Data structures and algorithm questions are important part of any programming job interview, whether Java interview, C, C++ interview or any other programming language. Since data structures are core programming concept, it’s mandatory for all programmers, to know basic data structures like stack, linked list, queue, array, tree, and graph.
One of the most popular questions from data structures and algorithm mostly asked during the interview. Since many programmers know that, in order to find length of linked list we need to first traverse through linked list till we find last node, which is pointing to null. Then in second pass we can find middle element by traversing only half of length.
Linked List
In order to find middle element of linked list in one pass, you need to maintain two pointers, one increment at each node while other increments after two nodes at a time. By having this arrangement, when first pointer reaches end, second pointer will point to middle element of linked list. See the following C program.
For example, if given linked list is 10->20->30->40->50 then output should be 30. If there are even nodes, then there would be two middle nodes, we need to print second middle element.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | #include <stdio.h> #include <stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; /* function to insert a node at the front */ void push(struct Node **head_ref, int new_data) { // create and a allocate a new node struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // insert in the data in node new_node->data = new_data; // Make next of new node as head new_node->next = (*head_ref); // move the head to point to the new node (*head_ref) = new_node; } /* Function to get the middle of the linked list*/ void printMiddle(struct Node *head) { struct Node *slow_ptr = head; struct Node *fast_ptr = head; if (head!=NULL) { //the only logic is to traverse the linked list with two pointers //one at normal speed and other twice the speed of first //when the fast pointer reaches to the end, slow pointer will be in //the middle of the linted list while (fast_ptr != NULL && fast_ptr->next != NULL) { fast_ptr = fast_ptr->next->next; slow_ptr = slow_ptr->next; } printf("The middle element is [%d]\n\n", slow_ptr->data); } } int main() { // declare an empty list struct Node* head = NULL; // Create a new linked list 10->20->30->40->50 */ push(&head, 10); push(&head, 20); push(&head, 30); push(&head, 40); push(&head, 50); // print the middle element from the linked list printMiddle(head); return 0; } |
Output of the program is:
The middle element is [30]
