Difficulty: Easy

Understanding the Problem

Problem Description

Given a non-empty, 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

1. Two-Pass: Find the length of the linked list and return the (length/2)th node.
2. One-Pass: 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. Two-Pass

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, increment ``` p ``` ``` length/2 ``` times. Now, the ``` p ``` is at the middle of the linked list node. Return the value at ``` p ```

Pseudo Code

``````int middleNode(ListNode head) {
int l=0
while (p != null) {
p = p.next
l = l + 1
}
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 the ``` head ``` ?
• Which node will be returned if the length of the linked list is even?
• What if the linked list forms a loop?

2. One-Pass

Another way to solve this problem is to use a little trick. Instead of traversing twice, we can create two-pointers ``` 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 ``` and ``` fast_ptr ``` pointing to the head initially.
• Increment ``` fast_ptr ``` by ``` 2 ``` and slow_ptr by ``` 1 ``` positions until ``` fast_ptr ``` and ``` fast_ptr.next ``` is not ``` NULL ```
• Return the value at ``` slow_ptr ``` .

Pseudo Code

``````int middleNode(ListNode 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 ``` and ``` fast.next != null ``` ?
• Do both the discussed approaches affect the running time?

Suggested Problems To Solve

Happy coding!

Enjoy Algorithms.