Middle Of Linked List
Given the head node of the singly linked list, return a pointer pointing to the middle of the linked list.

If there are an odd number of elements, return the middle element if there are even elements return the one which is farther from the head node.

For example, let the linked list be 1-2-3-4-null

Since the number of elements in this linked list is 4 so we have 2 middle elements, i.e. 2 and 3, but we return 3 as it is farther from the head node, i.e. 1.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases. The next ‘2*T’ lines represent the ‘T’ test cases. The first and only line of each test case contains integers denoting the nodes of the linked list. Each line is guaranteed to have -1 at the end to signify the end of the linked list.

Output Format :

For each test case, return a pointer pointing to the node which is at the middle of the linked list. If no midpoint exists, return a null pointer.

Note :

1.You do not need to print anything, it has already been taken care of. Just implement the given function. 2.For a linked list of size 1, the head node is the midpoint. 3.If no midpoint exists, return a null pointer.

Constraints :

1

Question

Middle Of Linked List

Given the head node of the singly linked list, return a pointer pointing to the middle of the linked list.

If there are an odd number of elements, return the middle element if there are even elements return the one which is farther from the head node.

For example, let the linked list be 1->2->3->4->null

add-image

Since the number of elements in this linked list is 4 so we have 2 middle elements, i.e. 2 and 3, but we return 3 as it is farther from the head node, i.e. 1.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘2*T’ lines represent the ‘T’ test cases.

The first and only line of each test case contains integers denoting the nodes of the linked list. Each line is guaranteed to have -1 at the end to signify the end of the linked list.

Output Format :

For each test case, return a pointer pointing to the node which is at the middle of the linked list. If no midpoint exists, return a null pointer.

Note :

1.You do not need to print anything, it has already been taken care of. Just implement the given function.

2.For a linked list of size 1, the head node is the midpoint.

3.If no midpoint exists, return a null pointer.

Constraints :

1 <= T <= 50
0 <= N <= 4*10^4
-10^9 <= data <= 10^9 
data ≠ -1

Where 'N' is the number of nodes and 'data' is the value of nodes.

Time Limit: 1 sec

Accepted Answer

Given the head node of a singly linked list, return a pointer to the middle node. If there are an odd number of elements, return the middle element. If there are even elements, return the one farther from the head node.

Traverse the linked list using two pointers, one moving one node at a time and the other moving two nodes at a time.
When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.
If the number of elements is even, return the second middle node.

Accepted Answer

Count Nodes Approach

If we want to know the midpoint of any linked list, it is very easy to do so if we know the number of elements in the linked list.
We take a pointer ‘p’ and use it to traverse the linked list and until we find NULL we increment a variable ‘count’ to count the number of elements in the linked list.
We then divide the number of elements by 2 to get the position of the middle element of the linked list.
Finally, we traverse through the first n/2 elements of the list and return the pointer of the middle element of the linked list.

We can take the Following Approach:

Take a pointer ‘p’ to traverse the linked list, initially pointing to head node.
Take a variable ‘numberOfNodes’ to count the number of nodes in the linked list.
Take a variable ‘mid’ and initialize it with ‘numberOfNodes/2’(middle of Linked List).
Finally, take a pointer ‘ptr’ and traverse through ‘mid’ number of nodes.
Return ‘ptr’ which is now at the middle of the linked list.

Space Complexity: O(1)Explanation:

O(1),

We are using constant space.

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ denotes the number of elements in the Linked List

Since we need to traverse the linked list twice first to find the number of elements and secondly again to find the middle node the overall complexity is the order of ‘N’.

Accepted Answer

Two Pointers Approach

We can find the midpoint of the linked list without finding the number of elements.
Simply take 2 pointers ‘fast’ and ‘slow’.
Fast pointer jumps 2 places and slow jumps 1 place.
Now when ‘fast’ pointer is at the end of the linked list the ‘slow’ pointer will be at the middle of the linked list.
Finally, we return the ‘slow’ pointer.

Keeping all that in mind we can use the following strategy to find the middle element.

If the head is NULL, we simply return HEAD.
If there is only one element in the linked list, we simply return it as it is the midpoint.
Otherwise, we initialise 2 pointers ‘fast’ and ‘slow’ both poiniting to head initially.
We traverse the linked list until fast is the last element or fast is beyond the linked list i.e it points to NULL.
In each iteration, the ‘fast’ pointer jumps 2 times faster as compared to ‘slow’ pointer.
Finally, once the loop terminates, ‘slow’ pointer will be pointing to the middle element of the linked list, hence we return the ‘slow’ pointer.