Middle of the Linked List - Leetcode #876

Middle of the Linked List - Leetcode #876

·

3 min read

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.

problem links: leetcode, geekforgeeks.

Example 1:

Input: head = [1,2,3,4,5] 
Output: [3,4,5]

Explanation: The middle node of the list is node 3.

Example 2:

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.

Constraints:

  • The number of nodes in the list is in the range [1, 100].

  • 1 <= Node.val <= 100

Intuition

The first solution that everyone thought of first finds the length of the list by traversing it and then traversing it back again for half the length.

You can say this is the brute force approach if we just think we can come up with a better approach. We can use TotrtoiseaHare Method slow and fast pointers approach to find the mid of the list in just one go, in fact, we don't even have to traverse the list completely.

The slow pointer moves to the next pointer while the fast pointer jumps twice.

Approach

  1. Declare and initialize slow and fast pointers with the head pointer.

  2. Now we have to iterate until we encounter any one condition where either fast is null or fast->next is null.

  3. In every iteration move the slow pointer to the next and the fast pointer to the next's next.

  4. When the loop got terminated, the slow pointer will be representing the middle of the linked list.

Example:

Consider the linked list

[1] → [2] → [3] → [4] → [5]

First iteration: Fast pointer moves from [1] to [3]. The slow pointer moves from [1] to [2].

Slow Pointer (S) Fast Pointer (F)

[2] [3]

Second iteration: Fast pointer moves from [3] to [5]. The slow pointer moves from [2] to [3].

Slow Pointer (S) Fast Pointer (F)

[3] [5]

Termination: The fast pointer reaches the end of the linked list (in this case [5]). At this point, the slow pointer is pointing to the middle element, which is [3].

[1] → [2] → [3] → [4] → [5]

Slow Pointer (S) Fast Pointer (F)

[3] [5] (end of linked list)

So, by using the slow and fast pointers, we can easily find the middle element of the linked list in linear time and with a constant amount of extra space.

Solution

C++

class Solution {
public:
    ListNode* middleNode(ListNode* head) {

        ListNode* slow = head, *fast = head;

        while(fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};

Middle of the Linked List Solution in c++

Java

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}

Middle of the Linked List Solution in Java

Time Complexity

if n is the number of nodes in the linked list. Then the worst-case time complexity will be O(n). As the slow and fast pointers iterated over the linked list once., the max number of iterations done is n/2

Space Complexity

The space complexity of this solution is O(1) or constant space complexity. As we only require slow and fast pointers which are constant variables, regardless of the linked list size.


Thank you for reading the post, I hope this would have helped you to understand the question better and the solution helped you to get a clear understanding of the approach used.

Feel free to drop any comments, I would love to solve your queries and improve my solution.

Did you find this article valuable?

Support Geek Aid by becoming a sponsor. Any amount is appreciated!