Question
A node that made by Linked List is given. You need to return the middle of the node.
If the length of the node is odd, return the second middle node.
Solution
There are some solutions to solve this question. I will introduce two solutions to you, two-loop and two-pointer.
In the first solution, I explore all elements to check the length of the node and calculate the middle of the length. Next, I explore again until the node reaches the center of the node. And, return the current node.
In the second solution, I defined a two-pointer named "slow" and "fast". The slow pointer moves one each node. On the other hand, the fast pointer move by two-step at once. When the fast pointer can not move the next node, the slow pointer is gonna be located in the middle of the node. So, return the current slow pointer as an answer.
Submissions
Here is the result.
# two pointer solution
Runtime: 20 ms, faster than 96.54% of Python3 online submissions for Middle of the Linked List.
Memory Usage: 13.7 MB, less than 7.14% of Python3 online submissions for Middle of the Linked List.
# Loop twice solution
Time complexity: O(n + n/2) -> O(n)
Space complexity: O(1)
# two pointer solution
Time complexity: O(n/2) -> O(n)
Space complexity: O(1)
The order is gonna be O(n) in the first solution even thoughI loop the node twice. It is because a constant number is ignored when we calculate the order. Technically, time complexity seems like O(n + n/2), but it is O(n).
Space is O(1). I copied the original node but it is constant, which means that it will not be expanding.
The time complexity of the second solution looks the same as the first one. I loop the node by half of the node. But time complexity is O(n). Space is O(1). The slow and fast pointer is constant as well.
Here is my python code.
# loop twice
# Time complexity: O(n + n/2) -> O(n)
# Space complexity: O(1)
def middleNode(self, head: ListNode) -> ListNode:
length: int = 0
copy: ListNode = head
while copy:
length += 1
copy = copy.next
mid: int = length // 2
while mid > 0:
head = head.next
mid -= 1
return head
# two pointer
# Time complexity: O(n/2) -> O(n)
# Space complexity: O(1)
def middleNode(self, head: ListNode) -> ListNode:
slow: ListNode = head
fast: ListNode = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
https://github.com/nk18chi/leetcode/blob/master/solutions/middle_of_the_linked_list/index.py
