LinkedList Questions: Middle Element of Linked List - Naive Approach

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,

1. Question Link ❓
2. Possible Explanation 📝
3. Documented C++ Code 🧹
4. 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.

https://leetcode.com/problems/middle-of-the-linked-list/

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

Explanation

The naive approach is very simple but it is important to understand what & why we are doing this to fully understand the optimized approach.

1. Find the length of LinkedList → L

2. Find the position (from start) of the node to be deleted: floor(L/2) + 1 → K

   • eg: for L = 5, required node is 3 = floor(5/2) + 1
   • eg: for L = 6, required node is 4 = floor(6/2) + 1
3. Reach the Kth node in K-1 iterations and return it.

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 *temp = head;
        int count = 0;

        //- finding length of LL : O(n)
        while (temp)
        {
            count++;
            temp = temp->next;
        }

        //pointing temp to head again
        temp = head;
        int nodeNo = count / 2 + 1; //doesn't matter if count is odd or even

        //-Time: O(k-1)
        //If I want to reach kth node, I need to go k-1 deep
        for (int i = 1; i <= nodeNo - 1; i++)
        {

            temp = temp->next;
        }
        head = temp;
        return head;
    }

Complexity Analysis

Time Complexity: O(n)

O(n) for finding length of List + O(n/2) for reaching the required node = O(n)

Space Complexity: O(1)

We didn't use any extra space