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.
Final result: Middle element of the list 3.