Solution to the Middle of the Linked List interview problem [+ ВИДЕО]

The video provides a more detailed explanation of each solution.

Formulation of the problem

Link to the task: https://leetcode.com/problems/middle-of-the-linked-list

The pointer is given head to the beginning of a singly linked list, you need to return the middle node of the list.

If there are two middle nodes, you need to return the second middle node.

1. Solution using an array

An approach

Converting a list to an array makes it easier to access elements by index. We iterate over the list and store all nodes in an array, since index access in an array takes constant time. O(1). After that we can easily find the middle element by simply taking the element by index len(items) // 2

Algorithm

Loop through the list and save all its elements into an array.
Determine the index of the middle element of the array.
Return the element at this index.

Solution code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        items = []

        while head: #None
            items.append(head)
            head = head.next
        
        return items[len(items) // 2]

Complexity of the algorithm

• By time: O(n), where n is the number of elements in the list.

• By memory: O(n) since we store all the elements of the list into an array.

Visualization

Original list: 1 -> 2 -> 3 -> 4 -> 5
Array after traversing the list: [1, 2, 3, 4, 5]
Index of the middle element: 5 // 2 = 2
Middle element in array: 3
0 1 2 3 4 [1, 2, {3}, 4, 5]

2. Solution with list length calculation

An approach

In this approach, we first count the number of elements in the list to know exactly how many nodes it contains. By counting the number of nodes, we can determine the index of the middle element as length // 2. Then, walking the list a second time, we stop at that index and return the corresponding node.

Algorithm

Loop through the list and count the number of elements.

Walk the list again to the middle element and return it.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        count = self.count(head)

        for _ in range(count // 2):
            head = head.next
        
        return head
    
    def count(self, head):
        res = 0
        while head:
            res += 1
            head = head.next
        return res

Complexity of the algorithm

• By time: O(n), where n is the number of elements in the list.

• By memory: O(1) since we don't use any extra memory.

Visualization

Original list: 1 -> 2 -> 3 -> 4 -> 5
Passage 1: Calculating the length of a list
• List length: 5
Average index: 5 // 2 = 2
Passage 2: Getting the middle element
• We go through the nodes to the index that we calculated in step 3:
1 (0), 2 (1), 3 (2)
Middle element: 3

3. Solution using fast and slow pointer method

An approach

This method uses two pointers: a fast pointer and a slow pointer. The fast pointer moves two nodes at a time, while the slow pointer moves one at a time. When the fast pointer reaches the end of the list or goes beyond the end of the list, the slow pointer is in the middle. This is because the fast pointer moves twice as many nodes in the same amount of time. This method is efficient because it only requires one pass through the list and uses minimal extra space.

Algorithm

Initialize two pointers, fast and slow, that point to the beginning of the list.
Move the slow pointer one step and the fast pointer two steps until the fast pointer reaches the end of the list.
When the fast pointer reaches the end of the list or goes beyond its bounds, the slow pointer will be on the middle element.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        return slow

Complexity of the algorithm

• By time: O(n), where n is the number of elements in the list.

• By memory: O(1), since we only use two pointers.

Visualization

Original list: 1 -> 2 -> 3 -> 4 -> 5
Starting position:
• Slow pointer (S) to 1
• Quick pointer (F) to 1
Step 1:
• S: 2 (moves 1 knot forward)
• F: 3 (moves 2 knots forward)
• List: 1 -> [2 (S)] -> 3 -> [4 (F)] -> 5
Step 2:
• S: 3 (moves 1 knot forward)
• F: 5 (moves 2 knots forward)
• List: 1 -> 2 -> [3 (S)] -> 4 -> [5 (F)]
End:
• The fast pointer (F) reaches the end of the list or goes beyond its bounds.
• The slow pointer (S) is at 3, which is the middle element.