Problem 45 - Middle of the Linked List
Explore our archive for previous posts.
Question
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
Approach
This problem involves finding the middle node of a linked list. Here's a high-level approach:
Two-Pointer Technique: Use two pointers, one slow and one fast, to traverse the linked list.
Move at Different Speeds: Advance the slow pointer by one step and the fast pointer by two steps.
Find the Middle: When the fast pointer reaches the end of the list, the slow pointer will be at the middle.
Solution
Solve it here
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
// Base case: If the list is empty or has only one node, return the head
if (head == null || head.next == null) {
return head;
}
// Initialize two pointers, slow and fast, starting from the head
ListNode slow = head;
ListNode fast = head;
// Traverse the list with different speeds
while (fast.next != null && fast.next.next != null) {
// Move slow pointer by one step
slow = slow.next;
// Move fast pointer by two steps
fast = fast.next.next;
}
// Check if the length of the list is odd or even
if (fast.next == null) { // Odd length
return slow;
} else { // Even length
return slow.next;
}
}
}Time and space complexity
Time Complexity: The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. The fast pointer traverses the list twice but in half the time.
Space Complexity: The space complexity is O(1) as we only use a constant amount of extra space for the two pointers. The algorithm is performed in-place and does not require additional data structures.
Explore more?
Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!
