Middle of the Linked List
Description
- Given the
headof a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.
Constraints
- The number of nodes in the list is in the range
[1, 100]. 1 <= Node.val <= 100
Test Cases
-
Input:
head = [1,2,3,4,5,6]
Output:[4,5,6] -
Input:
head = [1,2,3,4,5]
Output:[3,4,5]
Code
Approach 1: Using length of the list
Explanation
- Find the
lengthof the list. - Traverse the list till the middle of the list. (length/2)
- Return the node at the
middleof the list.
Analysis
- Time Complexity:
O(n) - Space Complexity:
O(1)
Approach 2: Using slow and fast pointer
Explanation
- Initialize two pointers
slowandfastto the head of the list. - Traverse the list with
fastpointer moving two nodes at a time andslowpointer moving one node at a time. - When
fastpointer reaches the end of the list,slowpointer will be at the middle of the list. - Return the node at the middle of the list.
Analysis
- Time Complexity:
O(n) - Space Complexity:
O(1)