876. Middle of the Linked List

Hello, reader 👋🏽 ! Welcome to day 65 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 876. Middle of the Linked List.

🤔 Problem Statement

Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
E.g:
- head = [1,2,3,4,5] => [3,4,5]
- head = [1,2,3,4,5,6] => [4,5,6]

💬 Thought Process - Return the length/2 element

The easiest approach to solve this is to get the length len of the list and then traverse until the len/2 element.
To get the length of the list, we can keep an integer counter integer initialised to 0 and then keep incrementing it until we reach the end of the list.
We'll do a second traversal with a counter initialised to 0 until the counter reaches the half length len/2.

👩🏽‍💻 Solution -Return length/2 element

Below is the code for the approach using getting the length and returning length/2 element.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null) return head;

        int length = getLength(head);
        int halfLen = length / 2;

        ListNode ptr = head;
        while(ptr != null && halfLen > 0) {
            halfLen--;
            ptr = ptr.next;
        }

        return ptr;
    }

    private int getLength(ListNode head) {
        ListNode temp = head;
        int length = 0;

        while(temp != null) {
            temp = temp.next;
            length++;
        }

        return length;
    }
}

Time Complexity: O(n)
  - n = number of nodes in the list
Space Complexity: O(1)

💬 Thought Process - Two Pointers

In the previous approach, we are iterating the list twice- once to get the length and one more to reach the half of the list.
Instead of doing two iterations, we can use two pointers such that there's a slow and fast pointer.
The fast pointer runs twice as fast as the slow pointer and the slow pointer is iterates in order over every item.
It can be seen that when the fast pointer reaches the last item (in case of list with odd length) or when the fast pointer becomes null (in case of list with even length), the slow pointer would be pointing the middle item in the list.
Hence with a single iteration and two pointers, we can reach the middle element of the list.
Below are the images shown with the slow and fast pointer illustrated for lists with:
1. Odd Length

![Slow and fast pointer approach in list with odd length](https://cdn.hashnode.com/res/hashnode/image/upload/v1670221524801/BcwqwWTx6.png align="left")

2.  Even Length


![](https://cdn.hashnode.com/res/hashnode/image/upload/v1670221658217/pPEtzz7bU.png align="left")

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null) return head;

        ListNode slowPtr = head, fastPtr = head;
        while(fastPtr != null && fastPtr.next != null) {
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
        }

        return slowPtr;
    }
}

Time Complexity: O(n)
  - n = number of nodes in the list
Space Complexity: O(1)

You can find the link to the GitHub repo for this question here: 876. Middle of the Linked List.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian