Write a C function to print the middle of a linked list

Intoduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given a linked list. We have to find the middle of the linked list.

Problem Statement Understanding

Let's suppose we have a linked list whose length is L, then the middle of the linked list will be the (L/2)th node of the linked list.

Suppose the given list is 5 → 10 → 3 → 4 → 8.

  • The length of this linked list is 5.
  • So, (5/2) = 2nd node will be the middle node of the linked list.
  • The middle of the linked list will be the node at 2nd position, which is 3, considering 0 based indexing.

Taking another example, let’s assume that the given linked list 1 → 3 → 5 → 7 → 9 → 11.

  • In this case, the length of this linked list is 6. So, (6/2) = 3rd node will be the middle node of the linked list.
  • The middle of the linked list will be the node at 3rd position, which is 7, considering 0 based indexing.

Now, I think from the above examples, the problem statement is clear. Let’s see how we can approach it.

Before moving to the further to approach section, try to think about how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

There are two solutions to this problem. One is the naive one and the second one is the optimal solution. The naive solution requires two traversals of the list, while the optimal solution only requires a single traversal of the linked list.

Let's have a glance at the naive approach and then see what we can do to optimize it.

Approach and Algorithm (Naive approach)

Here, in this approach, we first calculate the length of the list. Let the length be len.

  • Now, we traverse till the (len/2)th node and print it as it is obviously the middle node of the list.

This is the naive approach to solve this problem, but as we are preparing for coding interviews of big companies, we should be familiar with technique to find the middle node of the linked list without finding the length first.

The optimal solution requires a single traversal of the linked list and is the best way to find the middle of a linked list.

Time Complexity: O(N) - two traversals required.

Space Complexity: O(1), as only temporary variables are being created.

Now, let us discuss the approach in which we can find the middle of a linked list with a single traversal.

What if we start by taking two pointers, say slow and fast, and make both of them point to the head initially.

  • Now, what will happen if we make the slow jump one place and the fast jump two places (fast moving with twice the speed of slow).
  • If we notice carefully, by doing the above step, when the fast will reach the end of the list, the slow will be pointing to the middle of the list. With the help of this technique, we can reach the middle node of a linked list in a single pass.

Note: The reason why our slow pointer will be pointing to the middle of the linked list when the fast pointer is at the end is that, as our slow pointer is travelling with half the speed of fast pointer so when the fast pointer will reach the end of the linked list, till that time slow pointer will have only travelled half the distance as travelled by fast pointer and hence it will be at the middle of the linked list.

Do you know what the above-explained method is called?

  • This method is called the tortoise and hare method or the slow and fast pointer method. The slow and fast pointer method has been explained in detail in the approach section and the dry run.

Let us have a glance at the approach.

Approach (Optimal)

Let us see what the slow and fast pointer technique is:

  • Initially, both the pointers will point to the head of the linked list.
  • Then, we will move both of the pointers.
    • The fast pointer will jump two places, whereas the slow pointer will one place.
  • When the fast pointer will reach the end of the linked list, the slow pointer will be pointing to the middle of the linked list.

Algorithm

  • Create two pointers say slow and fast. Initially, point both the slow and the fast to the head of the list.
  • Now, the slow will jump one place, and the fast will jump two places until the fast reaches the end of the list.
  • When the fast pointer reaches the end of the list, the slow will be pointing to the middle of the list.
  • In the end, return the data of the slow pointer, as the slow will be pointing to the middle of the list.

Dry Run

![](https://blog.prepbytes.com/wp-content/uploads/2021/10/p_1-5.png)

Code Implementation

#include
#include

// Node structure of a linked list node
struct Node
{
    int data;
    struct Node* next;
};

// Using this function we will find and print the middle of the linked list
void findMiddle(struct Node *head)
{
    struct Node *slow_ptr = head;
    struct Node *fast_ptr = head;

    if (head!=NULL)
    {
        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);
    }
}

// Using this function we will create a new node and will insert at the beginning of the list
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node =
        (struct Node*) malloc(sizeof(struct Node));

    new_node->data = new_data;

    new_node->next = (*head_ref);

    (*head_ref) = new_node;
}

// Using this function we will print the linked list
void printList(struct Node *ptr)
{
    while (ptr != NULL)
    {
        printf("%d->", ptr->data);
        ptr = ptr->next;
    }
    printf("NULL\n");
}

// Driver Function
int main()
{
    struct Node* head = NULL;
    int i;
    push(&head,8);
    push(&head,4);
    push(&head,15);
    push(&head,10);
    push(&head,5);
    printf("The Linked List is : ");
    printList(head);
    findMiddle(head);
    return 0;
}

Output:

The Linked List is : 5->10->15->4->8->NULL
The middle element is 15

Time Complexity: O(n), a single list traversal is needed.

So, in this article, we have tried to explain the most efficient approach to find the middle of a linked list. This is an important concept when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Implementing a Linked List in Java using Class
Next post Linked List – Inserting a node

Leave a Reply

Your email address will not be published. Required fields are marked *