## DEV Community is a community of 722,735 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. Kathan Vakharia

Posted on

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,

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.

💡 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 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)
{
int count = 0;

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

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;
}
}
``````

## 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