Middle of the Linked List
Difficulty: Easy
Understanding the Problem
Problem Description
Given a nonempty, singly linked list with head node
head
, write a program to return a
middle node of the linked list.
If there are even nodes, then there would be two middle nodes, we need to print the second middle element.
Example 1
Input: 11>2>13>44>5
Output: 13
Explanation: The middle element of the linked list is 13.
Example 2
Input: 10>2>34>24>15>60
Output: 24
Explanation: As there are even number of nodes, return 24 as it is the second node among two middle elements.
Solutions
 TwoPass: Find the length of the linked list and return the (length/2)th node.
 OnePass: Use two pointers, the 2nd pointer should traverse twice as fast at the first.
Before moving forward with the question, you must understand the properties of a linked list .
You can try this problem here.
1. TwoPass
The question demands to find the middle of a singly linked list. We can simply find the total length of the linked list, in this way we can identify which node falls in the middle. To find the middle node, we can traverse again until we reach
(length/2)th
node.
Solution Steps

Create a pointer
p
, pointing to the head. 
Iterate over the linked list until
p
reaches to the end of the linked list, thereby find the length of the list. 
Set
p
to head again. Now, incrementp
length/2
times. Now, thep
is at the middle of the linked list node. Return the value atp
Pseudo Code
int middleNode(ListNode head) {
int l=0
ListNode p = head
while (p != null) {
p = p.next
l = l + 1
}
p = head
int c = 0
while (c < l/2) {
p = p.next
c = c + 1
}
return p.data
}
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
Critical Ideas To Think

Why did we reinitialize
p
with thehead
?  Which node will be returned if the length of the linked list is even?
 What if the linked list forms a loop?
2. OnePass
Another way to solve this problem is to use a little trick. Instead of traversing twice, we can create twopointers
say slow_ptr
and
fast_ptr.
We can make the
fast_ptr
twice as fast as
slow_ptr
. So, When the
fast_ptr
will reach to the end of the linked list,
slow_ptr
would still be at the middle, thereby pointing to the mid of the linked list.
Solutions Steps

Create
slow_ptr
andfast_ptr
pointing to the head initially. 
Increment
fast_ptr
by2
and slow_ptr by1
positions untilfast_ptr
andfast_ptr.next
is notNULL

Return the value at
slow_ptr
.
Pseudo Code
int middleNode(ListNode head) {
ListNode slow = head
ListNode fast = head
while (fast != null and fast.next != null) {
slow = slow.next
fast = fast.next.next
}
return slow.data
}
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
Critical Ideas To Think
 Why did we use two pointers?

Why did we iterate until
fast != null
andfast.next != null
?  Do both the discussed approaches affect the running time?
Comparison Of Different Approaches
Suggested Problems To Solve
 Remove Duplicates from Sorted List
 Merge Sort on Linked List
 Check if a singly linked list is a palindrome
 Detect and Remove Loop in a Linked List
 Sort a linked list using insertion sort
 Remove Nth Node from List End
Happy coding!
Enjoy Algorithms.