Digging around leetcode #876 Middle of the Linked List

Today when I repeated the solution for leetcode #876 Middle of the Linked List, I thought suddenly. What if we need to return the first middle element, not the second?

Let me remind you. The list can contain an odd number of elements:

linked list when length is odd

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Or list’s length can be even:

sample when length is even

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

By the description of the problem, we should return the second element in this case:

> If there are two middle nodes, return the second middle node.

But, what if?..

I remember a template for the leftmost and rightmost binary search. There’s an important difference when calculating the middle element.

For leftmost search, mid is rounded to zero:

public int Search_leftmost(int[] nums, int target)
{
    if (nums.Length == 0)
        return -1;

    var left = 0;
    var right = nums.Length - 1;

    while (left < right)
    {
        var mid = left + (right - left) / 2;

        if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
    
    if(nums[left] == target)
        return left;

    return -1;
}

And for the rightmost search, the mid is rounded to the biggest number:

public int Search_rightmost(int[] nums, int target)
{
    if(nums.Length == 0)
        return -1;
        
    var left = 0;
    var right = nums.Length - 1;
    
    while (left < right)
    {
        var mid = 1 + left + (right - left) / 2;
        
        if(nums[mid] > target)
            right = mid - 1;
        else
            left = mid;
    }
    
    if(nums[left] == target)
        return left;

    return -1;
}

So, I saw a connection between these problems and tried to solve this new problem.

The first version was a two-pass solution with linear time complexity and constant space complexity:

public ListNode MiddleNode(ListNode head)
{
    var counter = 0;
    var node = head;
    while(node != null)
    {
        counter++;
        node = node.next;
    }

    var slow = head;
    ListNode prevSlow = null;
    var fast = head;
    while(fast != null && fast.next != null)
    {
        prevSlow = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return counter % 2 == 1 ? slow : prevSlow;
}

I calculate the node’s count, then return either slow pointer (for odd length) or prev element before slow pointer (when the length is even).

Can I improve this solution and find a one-pass solution? I thought a lot and found a pattern. If the linked list has an even length — the fast pointer is null. And when the list has an odd length — the fast.next is null.

So, I wrote a second version:

public ListNode MiddleNode(ListNode head)
{
    var slow = head;
    ListNode prevSlow = null;
    var fast = head;
    while(fast != null && fast.next != null)
    {
        prevSlow = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return fast != null ? slow : prevSlow;
}

I can modify this solution to avoid using prevNode. With dummy node:

public ListNode MiddleNode(ListNode head)
{
    var fast = head;
    var unusedVal = 0;
    var dummyNode = new ListNode(unusedVal);
    dummyNode.next = head;
    var slow = dummyNode;
    while(fast != null && fast.next != null)
    {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return fast != null ? slow.next : slow;
}

or without:

public ListNode MiddleNode(ListNode head)
{
    var fast = head;
    ListNode slow = null;
    while(fast != null && fast.next != null)
    {
        slow = slow == null ? head : slow.next;
        fast = fast.next.next;
    }
    
    return fast != null ? slow.next : slow;
}

It’s just a minor variation, as I think.

But what’s the main point of this article?

It’s really useful to dig around your current problem. You can found something curious. I never think that I can determine if the length is even or odd without traversing the whole linked list. And now I know. Maybe, this could come in handy.

The second reason is that the real job interview problem could be different than described on leetcode. Just look at leetcode #415 Add Strings: here is a remark before solution:

> Facebook interviewers like this question and propose it in four main variations.

So, a good interviewer knows about leetcode and similar websites and can modify the original problem. And if you start your research when solving a problem, you can understand the problem deeply and train your brains to think more widely.

Are you agree with my conclusions? Please, post in the comments your opinion!