Solution: Middle of the Linked List

Let’s solve the Middle of the Linked List problem.

We'll cover the following

Statement

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node. This happens when the length of the list is even, and the second middle node occurs at length2\frac {length}{2}. Otherwise, if the length of the list is odd, the middle node occurs at length2+1\frac {length}{2}+1.

Constraints:

Let n be the number of nodes in a linked list.

  • 1≤1 \leq n ≤100\leq 100
  • 1≤1 \leq node.data ≤100\leq 100
  • head ≠\neq NULL

Solution 1: Brute force

We can first determine the length of the linked list; based on the length, we can then calculate the position of the middle node. If the length is even, the middle position will be half the length of the list. If the length is odd, the middle position will be half the length plus one.

The steps of the algorithm are given below:

  1. Implement a length function to determine the total number of nodes in the linked list. Iterate through the list, starting from the head, and increment a counter for each node encountered until reaching the end of the list.

  2. Initialize the node to the head of the linked list.

  3. Set mid to half of the length plus one.

  4. Traverse the linked list using a loop that runs mid - 1 times:

    a. In each iteration, advance the node to the next node.

  5. After the loop, the node points to the middle node of the linked list. Then, return the node.

Let’s look at the code for this solution below:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.