LinkedList Questions: [Optimal] Find Middle Element

In this series of posts, I will discuss coding questions on the LinkedList Data structure.
The posts in this series will be organized in the following way,
  • Question Link ❓
  • Possible Explanation 📝
  • Documented C++ Code 🧹
  • Time and Space Complexity Analysis ⌛🌌
  • The Question
    Given a non-empty, singly linked list with head node head, return a middle node of the linked list.
    If there are two middle nodes, return the second middle node.

    💡 Give yourself at least 15-20 mins to figure out the solution :)

    Explanation
    I hope you have read the previous article because I want to relate the ideas of both approaches rather than making you feel, an optimal solution is a completely new thing!

    👀 Observation: If you recall from the last post, we can reach the middle node after floor(L/2) iterations.

    Remember the above point, I'll come to this point after we see the algorithm.
    Here's the algorithm.
  • Initialize two pointers, fast and slow both pointing to head initially.
  • Move fast double the speed than slow untill fast becomes NULL or it has reached the last node.

    //pseudo code
    while fast!=NULL and fast->next != NULL
            fast = fast->next->next
            slow = slow->next
    
  • return slow .

  • Why does this work?
    First of all, we can either have an odd length linkedlist or an even length LinkedList.
  • Case 1: Odd length
    • fast will point to the last node after floor(L/2) iterations.
  • Case 2: Even Length
    • fast will become NULL after traversing the entire list in floor(L/2) iterations.
  • So no matter what the type of LinkedList, one of the loop termination conditions will hit after floor(L/2) iterations, and by that time slow would be pointing to the required middle node.
    C++ Code
    Definition of Linked List
    //Definition for singly-linked list.
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
    };
    Solution
    ListNode *middleNode(ListNode *head)
      {
          ListNode *fast;
          ListNode *slow;
          fast = slow = head;
    
          //make fast reach the end of the list by moving it double time the slow
          while (fast != nullptr && fast->next != nullptr)
          {
              fast = fast->next->next;
              slow = slow->next;
          }
          //* now slow will point to the required node
    
          return slow;
      }
    Complexity Analysis
    N: Length of Linked List.
    Time Complexity: O(N)
    We are doing O(N/2) iterations which asymptotically is the same as O(N)
    Space Complexity: O(1)
    We didn't use any extra space.

    47

    This website collects cookies to deliver better user experience

    LinkedList Questions: [Optimal] Find Middle Element