Find the middle of a given linked list data structure

Question: In given a Linked List,  find the middle of the list and print the number.

Input : -> 4-> 2-> 7-> 9-> 1

Output : 7

Before starting you have to must know about Linked list and how to create it and Inserting node (data) in LinkedList.

There is many approach to find middle number in LinkedList.

1.  Single pointer 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.

Output : -> 4-> 2-> 7-> 9-> 1
Middle node of linked List is 3
Middle node data is 7

Time Complexity: Time for finding the length of list + Time for locating middle node = O(n) + O(n) ≈ O(n)
Space Complexity: O(1)

2. Using 2 pointers

With 2 pointers to traverse the list ,we can find the middle of list with only one scan on the Linked List.

  • pointer1 travels one node at a time
  • pointe2 travels two nodes a time.

Thus, when pointe2 reaches the end of the Linked List, pointer1 will point at the middle of the Linked List.

Output: -> 4-> 2-> 7-> 9-> 1
Middle node data is 7

Time Complexity: O(n)
Space Complexity: O(1)

here is more LinkedList interview questions :

  1. Program for find n’th node from the end of a Linked List
  2. Reverse a Linked list data structure in java
  3. Inserting a new node in a linked list data structure
  4. Find Length of a Linked List data structure (Iterative and Recursive)

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.