Last Updated: 8 Dec, 2020
Middle Of Linked List
Easy
Asked in companies
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.
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.
Approaches
- 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.
- 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.