Table of contents
An Easy category problem where you can come up with a range of different ways to solve it. The fifth problem https://leetcode.com/problems/middle-of-the-linked-list/ of the December leetcoding challenge where linked lists are the subject of talk. I must say that my feelings toward linked lists are somewhat mixed. I like learning and solving problems with them but I haven't used them practically in software yet. I am yet to research their real-life use cases. Even so, I cannot help but marvel at how we can overcome the shortcomings of arrays with linked lists.
Problem breakdown
We are given the reference to the head pointer of a linked list and asked to return the middle node of the linked list. Now, if it was an array we could have simply halved the length of the list to get the index of the middle item and solved the problem however in the case of a linked list we don't know the length or the number of elements in the list.
There are multiple ways to go about doing so. As an easy first approach, we can use an array to store the elements, get the number of elements in that way and use counting to get the middle node. But this way we will run into problems when the linked lists will increase in size and taking extra space would just not be feasible.
My approach
We will use two pointer approach to solve this problem. One pointer will advance forward one step and the other will advance two steps at a time. After finishing the iteration the position of the first pointer will be that of the middle of the list.
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
Time and Space complexity
No extra space is used so space complexity is O(1) and time complexity is O(n) as we iterate through the array to get the middle node.
That's all for this problem. Let me know how you solved this problem as well. Thanks for reading.