Middle of the Linked List

We want to find the middle node of a singly linked list. If there are two middle nodes, we will return the second one. We’ll use the “tortoise and the hare” approach, also known as Floyd’s cycle-finding algorithm.

1. Initialize Two Pointers: We will use two pointers, slow and fast. slow will move one step at a time, while fast will move two steps at a time.
2. Move Pointers: We’ll move the pointers until fast reaches the end or the node before the end of the list.
3. Return the Middle Node: The slow pointer will be at the middle node when the fast pointer reaches the end.

Here is the code:

1
2
3
4
5
6
7

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

Example

• 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, which is the node with value 4.

Insights

• Time Complexity: The time complexity is (O(n)), where (n) is the number of nodes in the linked list.
• Space Complexity: The space complexity is (O(1)), as we only use a constant amount of extra space.
• Two Pointer Technique: This approach elegantly finds the middle of the list by using two pointers at different speeds.

1. Bruteforce Approach Iterate through the entire linked list We can use stack to keep track of all the elements We keep track of the current linked list When we reach the end of the linked list (we encounter nil) Pop the elements of the stack

2. Slow and Fast Pointers

   • When either the fast is null or fast.next is null

3. Terminating in the while loop The one element case provides the condition

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @return {ListNode}

def middle_node(head)
    slow = fast = head

    while !fast.nil? and !fast.next.nil?
        slow = slow.next
        fast = fast.next.next
    end
    slow
end