Count median in linked list

Question

Given a singly linked list, write a function to calculate and return the median value of the elements in the list. If the list has an odd number of elements, return the middle element; if it has an even number of elements, return the average of the two middle elements. The function should handle edge cases, such as an empty list, appropriately.

Codemia · Accepted Answer

To solve the problem of finding the median in a singly linked list, we can observe that the linked list does not allow random access to elements, making it less straightforward than an array. The median is defined as the middle value when the data set is sorted. In this case, the best approach is to traverse the list to count the total number of elements and then find the middle elements. This leads us to a two-pass solution: the first pass to count elements and the second pass to retrieve the median. The two pointers technique is not applicable here since we can't access the elements randomly, and the sliding window does not fit the problem's requirements either.

1. **Count the elements**: Iterate through the linked list to count the total number of nodes. This gives us the size of the list.
2. **Determine the median position(s)**: If the count is odd, the median is the middle element. If even, it's the average of the two middle elements.
3. **Retrieve the median**: Traverse the linked list again to reach the middle element(s) based on the total count.

**Example**: For a linked list `1 -> 3 -> 3 -> 6 -> 7 -> 8 -> 9`: 
- Count = 7 (odd), so median is the 4th element `6`. 
For a linked list `1 -> 2 -> 3 -> 4`: 
- Count = 4 (even), so median is (2 + 3) / 2 = 2.5.

Here’s the Python implementation of the described approach:

```python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def findMedian(head: ListNode) -> float:
    if not head:
        return 0.0  # Edge case for empty list

# Step 1: Count the number of elements
    count = 0
    current = head
    while current:
        count += 1
        current = current.next

# Step 2: Determine the median position(s)
    mid1 = count // 2
    mid2 = mid1 - 1 if count % 2 == 0 else mid1

# Step 3: Retrieve the median element(s)
    current = head
    for i in range(mid1 + 1):  # +1 to include mid1
        if i == mid1:
            median1 = current.val
        if i == mid2:
            median2 = current.val
        current = current.next

# Calculate median
    if count % 2 == 0:
        return (median1 + median2) / 2.0
    else:
        return median1
```

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. This is because we traverse the list twice - once to count the nodes and once to retrieve the median values. The space complexity is O(1) since we are using a constant amount of space regardless of the input size. This holds true even for edge cases like an empty list.

1. **Empty List**: The function should return 0.0 or handle it as defined in the requirements since there's no median in an empty list.
2. **Single Element List**: If the list has only one element, that element is the median.
3. **Two Elements List**: The median should be the average of the two elements.
4. **Large List**: Ensure that performance holds up with larger lists to confirm O(n) time complexity in practice.

Count median in linked list

Brex

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Brex Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string