Description

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:

1Input: head = [1,2,3,4,5]
2Output: [3,4,5]
3Explanation: The middle node of the list is node 3.

Example 2:

1Input: head = [1,2,3,4,5,6]
2Output: [4,5,6]
3Explanation: 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

Brute Force - Using Array

If we convert the list into array, then we can easily find the middle of the list using its middle index. However, to convert to the an array, we will require at least single iteration which will be time complexity O(n). This also requires new array of size n. In the problem constraint, we know that the list can be upto size 100. We can also track the size of the list when we iterate through the list to create a new array.

 1class Solution {
 2    public ListNode middleNode (ListNode head) {
 3        ListNode[] arr = new ListNode[100];
 4        int i = 0; // track size of the list
 5        while (head != null) {
 6            arr[i++] = head;
 7            head = head.next;
 8        }
 9        return arr[i / 2];
10    }
11}
  • Time Complexity: O(n) as we have to iterate through list once to populate an array.
  • Space Complexity: O(n) because we need to create an array of size n

Better Approach - Fast and Slow Pointers

This problem can be slowed with fast and slow pointers. The idea is to move fast pointer two position when slow pointer moves just single position. This way when the fast pointer reaches end of the list, the slow pointer will make it to the middle of the list.

 1class Solution {
 2    public ListNode middleNode (ListNode head) {
 3        ListNode slow = head;
 4        ListNode fast = head;
 5        while (fast != null && fast.next != null) {
 6            slow = slow.next;
 7            fast = fast.next.next;
 8        }
 9        return slow;
10    }
11}
  • Time Complexity: O(n)
  • Space Complexity: O(1)