Table of Contents
Introduction
A Linked List is a linear data structure that consists of nodes. Each Node contains a data field and a pointer to the next Node. In Linked List, unlike arrays, elements are not stored at contiguous memory locations but rather at different memory locations. The various elements in a linked list are linked together using pointers.
Linked List is one of the important topics from an interview perspective. Almost all the major companies ask questions related to Linked List in the initial stages. One of the most frequently asked questions by Top Product based companies, including Amazon, Flipkart, Adobe, is “Find the Middle Node of a Linked List.”
The problem statement says, “Given a Linked List and a head pointer pointing to the first node of a linked list, find the middle node of a Linked list”
Example for Linked List:
| Input Linked List | Output |
| 1->2->3->4->5->NULL | 3 |
| 10->20->30->40->NULL | 30 |
Note that in the case of an even number of nodes in the Linked List, there will be two middle nodes. In that case, we need to print the first middle element. The various approaches to solve this problem are discussed in detail along with code in Java.
Recommended: Please solve it on Codestudio before moving on to the solution.
Approach 1 For Middle Node of a Linked List
The middle node of a Linked List is the element at (Number of Nodes/2)th position. We need to find the element at this position.
The problem thus reduces to the following two steps:-
- Find the number of elements(count) in the Linked List
- Print the element at (count/2)th position
Algorithm:
Step 1) An obvious approach would be to iterate through the Linked List and maintain a count variable that will keep the count of the number of nodes in the Linked List.
In the code below, the getCount() method is used for this.
Step 2) Now again iterate through the List till count/2 and return the Node at count/2.
In the code below, findMiddleNode() method is used for this.
Code:
For the sake of simplicity, the below program uses only two methods for insertion of a new node in the Linked List
- push() -> To insert a node at the beginning of Linked List.
- insertAtLast() -> To insert a node at the end of the Linked List.
public class MiddleNode
{
Node head;
// Node class
class Node{
int key;
Node next;
Node(int data)
{
key = data;
next = null;
}
}
// Method for inserting node to the front
public void push(int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
// Method for inserting a node at the last
public void insertAtLast(int data)
{
Node new_node = new Node(data);
if(head == null){
head = new_node;
return;
}
Node temp = head;
while(temp.next != null)
{
temp = temp.next;
}
temp.next = new_node;
return;
}
// Method to get the count of number of nodes in the List
public int getCount()
{
int count = 0;
Node temp = head;
while(temp!= null)
{
count++;
temp = temp.next;
}
return count;
}
// Method to find the middle node of a linked list
public void findMiddleNode()
{
int count = getCount();
Node temp = head;
// If the number of nodes are even, then there are
// two middle nodes print the first middle node
if(count%2 == 0)
{
int i = (count/2) - 1;
while(i != 0)
{
temp = temp.next;
i--;
}
System.out.println(temp.key);
}
// If the number of nodes are even
else{
int i = (count/2);
while(i != 0)
{
temp = temp.next;
i--;
}
System.out.println(temp.key);
}
}
// A utility method to print the Linked List
public void printList()
{
Node temp = head;
while(temp != null)
{
System.out.print(temp.key + " ");
temp = temp.next;
}
}
public static void main(String []args)
{
MiddleNode ll = new MiddleNode();
// Making a linked list of odd number of nodes
// 1->2->3->4->5->NULL
ll.push(1);
ll.insertAtLast(2);
ll.insertAtLast(3);
ll.insertAtLast(4);
ll.insertAtLast(5);
System.out.println("Printing the original Linked List");
ll.printList();
System.out.println("\nThe middle node of a Linked list is");
ll.findMiddleNode();
// Making a linked list of even number of nodes
// 10->20->30->40->50->60->NULL
ll = new MiddleNode();
ll.push(10);
ll.insertAtLast(20);
ll.insertAtLast(30);
ll.insertAtLast(40);
ll.insertAtLast(50);
ll.insertAtLast(60);
System.out.println("Printing the original Linked List");
ll.printList();
System.out.println("\nThe middle node of a Linked list is");
ll.findMiddleNode();
}
}
The output of the above program is:
Printing the original Linked List 1 2 3 4 5 The middle node of a Linked List is 3 Printing the original Linked List 10 20 30 40 50 60 The middle node of a Linked List is 30
Complexity Analysis:
The Linked list is traversed two times. Once for the entire Linked List and second till the middle of Linked List. So the time complexity will be O(N) + O(N/2), which is equivalent to O(N), where N is the number of elements in the Linked List.
As no extra space is required, so the space complexity is O(1)
Approach 2 For Middle Node Linked List
Instead of traversing the Linked List twice, the middle node of a linked list can be found in a single traversal as well by using a two-pointer approach.
The idea is two use two pointers, slow and fast, respectively. Move the slow pointer by one step and the fast pointer by two steps. Proceeding this way, when the fast pointer will reach the end of the Linked List, the slow pointer will be at the middle of the Linked List.
Algorithm:
The approach is a slight variation of the Tortoise Hare Approach:
- Initially, both the pointers point to the first node of the Linked List. Move the slow pointer by one position and the fast pointer by two positions.
- The slow pointer now points to the second node and the fast pointer points to the third node respectively.
- The slow pointer is now pointing to the third node and the fast pointer is now pointing to the fifth node.
Clearly, we see that if the fast pointer cannot make a move or fast.next.next == null, then the slow pointer is at the middle node.
The approach works for a Linked list with an odd number of nodes as well as shown below.
- Initially, both the pointers are pointing to the first node of the linked list. Move the slow pointer by one position and the fast pointer by two positions.
- Now the slow pointer is pointing to the second node and the fast pointer is pointing to the third node of the Linked list.
- Now the slow pointer is pointing to the third node and the fast pointer is pointing to the last node as shown below.
It is clear from the above illustration that in the case of an even number of nodes in the linked list, the middle node will be reached once the fast pointer points to null, and in case of an odd number of nodes in the linked list, the middle node will be reached once the fast pointer points to the last node.
Code:
Below is the code to find the middle of the linked list using two pointer approach
// Two pointer approach to find the middle node of a linked list
public void findMiddleNode()
{
Node slowPtr = head;
Node fastPtr = head;
while(fastPtr.next != null && fastPtr.next.next != null)
{
fastPtr = fastPtr.next.next;
slowPtr = slowPtr.next;
}
System.out.println("Middle node of a linked list is : " + slowPtr.key);
}
Complexity Analysis:
The list is iterated once, so the time complexity of the above method is O(N), where N is the length of the Linked List
The space complexity is O(1) as no extra space is used.
Approach 3 For Linked List
If you are lucky enough that your interviewer allows you to use the Linked List class of collection framework, then finding the middle of the linked list becomes quite straightforward.
Code:
import java.util.LinkedList;
public class Main{
public static void main(String[]args)
{
LinkedList<Integer> ll = new LinkedList<>();
ll.add(10);
ll.add(20);
ll.add(30);
ll.addLast(40);
ll.addLast(100);
System.out.println("Given Linked list is : " + ll);
int mid = ll.get(ll.size()/2);
System.out.println("Middle node of a linked list is: " + mid);
}
}
The output of the above program is:
Given Linked list is: [10, 20, 30, 40, 100] Middle node of a linked list is: 30
While most interviewers prefer to ask for direct implementation, some interviewers might also ask specifically for the above approach so as to test the knowledge of the Collection Framework in Java.
Frequently Asked Questions
To find the middle element of a linked list, there are two possible approaches:
1. Iterate the list of elements once and count the number of nodes in the list. Once again iterate through the list this time only till the (count/2) position. The element at position (count/2) is the middle element.
2. Use two pointer approach as discussed above
The time complexity of both the approaches as discussed above is O(N) where N is the size of the linked list.
Yes a Linked list can contain duplicate elements.
Key Takeaways
This article discussed various approaches to find the middle node of a linked list. With this done you can now practice more questions related to the Linked List approach on Codestudio.
If you are new to programming and want to learn more about programming languages, do check out the guided path available for free and amazing courses offered by Coding Ninjas.
