Tackling Leetcode Problem 876: Middle of the Linked List
This is 6th continuing on the series of articles I've written detailing my experience learning data structures and algorithms using Large Language Models as instructors and confronting LeetCode problems.
Problem Statement
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
?
Example 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
Example 2:
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.
?
Constraints:
Initial Thoughts and Past Experiences
Discovering the middle of a linked list is actually part of the process on the implementation of Merge Sort for on the very same data structure.
A few days ago I was experimenting and concluded a Doubly linked list was what I needed to store a sorted order of elements in my database to minimize writings for a list I wanted to semantically make comparisons for in a way that I was able to easily insert new elements in the list when comparing pairs of them against a criteria such as 'importance' so most important items would pop on top.
I discovered that part of the functioning of Merge Sort is that it needs to recursively find the middle points of lists before joining them by comparing the elements by pairs. As part of that, I ended up discovering the exact same algorithm that works for a solution to this.
Just by reading the first part of the statement I already knew two pointers (which is actually a tag that I saw later on the problem) had to be used to come up with a solution.
That's what I started pursuing.
ChatGPT Interaction
The first time I confronted this problem, I hadn't started using ChatGPT for learning yet. And the second time, I came up with a solution for it right away. So, ChatGPT interactions weren't necessary.
Discoveries and Tricky Parts
I did have a moment of realization as soon as I read it, as I said before. I realized that the solution was about using two-pointers. One that was slow, another one that was faster.
The second time around, even though I remembered the approach to solving it, I was having trouble setting up the while so it would return the right node when the list has an even number of nodes.
An even number of nodes means there's no exact center node, and that there are two center ones rather. The problem specifically asks for the one to the right to be returned. So I was having trouble configuring the while under a condition that enabled me to have the slow pointer end up in that one when the condition didn't hold anymore.
Solution
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
i, j = head, head
while(j and j.next):
i = i.next
j = j.next.next
return i
As the solution involves two pointers, you declare two variables. You assign each one the head of the list, which is what you receive as input.
I guess I have seen other algorithms start on the second node instead of on the head for the fast pointer. But that probably requires a change in the condition the while loop functions under.
Then what you do is you check if j or j.next exists and if so the loop continues. Because if j.next == None we have reached the end.
i, as is the one to go slow, is going to be at that point where, the conditions break, in the middle of the list. Same if there's no j either.
Inside the while, we move the slow pointer one at a time to the next node. The fast pointer, in contrast, we move two at a time. So like pressing next twice. We access the next.next which makes results in having double the steps traveled with the fast pointer at any point (in respect to the slow pointer).
This makes it so that when the conditions breaks, and j is at the end, i is always going to be in the middle. Right in the middle node when the list has an even number of nodes, and on the right node to the middle when the number of nodes is even.
Optimization
This is also one of those problems, at least in Python, that has such a straightforward solution, you inevitably reach the optimal solution if you implement it.
More optimizations are not really possible. And as I can see from the rankings, there's not much involved in it. Apart from some strange modifications that undermine the simplicity of the code by holding more variables and using memory in other ways.
So I guess there's not any considerable space for optimization.
Learned
There are other instances of these types of problems where we have to think about two-pointers too, and the fact that two-pointers are a tag on LeetCode Questions implies that there are a lot of questions that you can use this to solve one way or another.
The algorithm for coming up with the middle of a linked list, though, is a super-specific tool to use when finding and returning exactly that from a linked list. So I guess in that regard, it's very specific.
Apart from that, a two-pointer approach can be used in many more contexts as I understand it. I know there are other two-pointer questions in the context of graphs and other data structures where they are useful. So it's good to have a little bit of a grasp on them.
In any way, two-pointers seem to be a rather concrete and very general conceptualization that depends on the specific problem at hand to decide how one would implement it.
The way I was using it in my code was that I'd trade one-to-one comparisons between elements for navigation because comparisons in my app request AI models through APIs, which is kind of expensive, and I decided to trade that for the navigation required to implement binary insertion on a linked list, part of that was obviously finding the middle of sub-sequences of a list for what this exact algorithm was used.
Further
The LeetCode platform itself was helpful. The solutions section, where people actually publish those sort of article-like posts explaining their solutions, was kind of helpful to figure out what the best approach to the condition inside or the condition for the while loop was.
For the binary insertion thing that I talked about, although it is tangentially related, I saw a Stack Overflow question that helped me understand the trade-off that I was making between navigation comparisons and computations versus AI comparisons for the binary insertion algorithm I ended up using in my app.