In the following article, we are going to check how to find the middle of the Linked List
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
Example 1:
Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3.
Example 2:
Input: head = [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
Constraints:
- The number of nodes in the list is in the range
[1, 100]. 1 <= Node.val <= 100
Solution:
We are solving the problem by using a fast pointer and a slow pointer, node_a is a fast pointer and node_b is a slow pointer. We are increasing the fast pointer by two and the slow pointer by one, when the fast pointer is at the end that time slow pointer is the middle.
public ListNode MiddleNode(ListNode head) {
ListNode node_a = head;
ListNode node_b = head;
while(node_a != null && node_a.next != null)
{
node_a = node_a.next.next;
node_b = node_b.next;
}
return node_b;
}Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)