Linked List - 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 (even length list), return the second middle node.

Input: head = [1, 2, 3, 4, 5]
Output: [3, 4, 5]
Explanation: The middle node has value 3. Returning node 3 and everything after it.

Input: head = [1, 2, 3, 4, 5, 6]
Output: [4, 5, 6]
Explanation: With 6 nodes there are two middle nodes (3 and 4). The second middle node (value 4) is returned.

The classic approach is to use two pointers where slow moves one step at a time and fast moves two steps at a time. When fast reaches the end, slow is at the middle.

Initialize both slow and fast at head.
While fast != null and fast.next != null, advance slow by 1 and fast by 2.
When the loop ends, slow is at the middle node. For even-length lists, this naturally gives the second middle.
Return slow.

class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } public class MiddleOfLinkedList { public ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; // move 1 step fast = fast.next.next; // move 2 steps } return slow; // slow is at the middle } }

Complexity Analysis:

Time complexity: O(n) where n is the number of nodes. The fast pointer traverses the list in n/2 iterations.
Space complexity: O(1) since only two pointer variables are used.