Middle Of Linked List

Easy
0/40
Average time to solve is 20m
315 upvotes
Asked in companies
SamsungInfosysCognizant

Problem statement

Given a singly linked list of 'N' nodes. The objective is to determine the middle node of a singly linked list. However, if the list has an even number of nodes, we return the second middle node.

Note: 
1. If the list is empty, the function immediately returns None because there is no middle node to find.
2. If the list has only one node, then the only node in the list is trivially the middle node, and the function returns that node.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'N', the size of the linked list.
The second line contains 'N' space-separated integers.


Output Format : 
The output contains all the integers from the middle node.


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


Sample Input 1 :
5
1 2 3 4 5
Sample Output 1 :
3 4 5
Explanation Of Sample Input 1 :

add-image

We can clearly see that there are 5 elements in the linked list therefore the middle node is the node with value '3'.
Sample Input 2 :
6
1 2 3 4 5 6
Sample Output 2 :
4 5 6
Explanation Of Sample Input 2 :

add-image

We can clearly see that there are 6 elements in the linked list and the middle nodes are  nodes with values 3 and 4 hence we return a second middle node having value '4'.
Constraints :
1 <= 'N' <= 10^4
0 <= 'data' <= 10^3 

Where 'N' is the length of the linked list.

Time Limit: 1 sec
Hint

Try to find the number of elements in the given Linked List.

Approaches (2)
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.
Time Complexity

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’.

Space Complexity

O(1), 

 

We are using constant space.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Middle Of Linked List
Full screen
Console