Linked Lists? Linked Lists! (Coding Blog) — Week 3
Yo. It’s time for some linked lists. I love these. Let’s get started.
(I still don’t really know how to start these).
Once again, this problem is from Elements of Programming Interviews in Python by Adnan Aziz, Tsung-Hsien Lee and Amit Prakash, and the solution is coded in Python 3. If you’re looking for a book to help you with your white board coding in Python/C++/Java, look for Elements of Programming Interviews in your preferred language.
Disclaimers aside, let’s get to it!
Problem: Test for Overlapping Non-Cyclic Linked Lists
Write a program that takes as input two cycle-free singly linked lists, and returns the first node that is common to both linked lists, or none if there is no overlapping.
It’s a pretty neat problem, take a moment to figure it out!
A simple brute force solution to this problem would be to check if each node in list 1 is the same as each node in list 2. This would require O(n²) time but O(1) space. Another solution would be to map each node to a hashmap and check if any nodes are the same. This would be O(n) time, but O(n) space. We can definitely do better than that.
Let’s look at this problem logically.
If there exists a node where these two lists converge, then they must share the same tail node. That also means the length of these two lists from the point they converge to the tail node must be the same length.
With that information, this problem becomes trivial.
You can easily determine the length of each list, ensure that each list starts at an equal length (by this I mean if list 1 is 10 nodes long and list 2 is 12 nodes long, we move the pointer pointing at the current node to node 3, which now makes list 2 also 10 nodes long), and then compare the node to see if they are the same. If they are, we return the node. If they are not, we check the next set of nodes and so on. If we get to the end of the lists, we return 0 as there are no common nodes.
Simple enough, let’s hop into the code!
First, we’ll create our function, but we’ll also create a nested function, length, which determines the length of the linked list. This function will simply traverse the given list while there are nodes, and then return the length of the list.
Now, we’ll declare variables for the length of each list. We’ll also swap the lists’ variables so that the longer list is always list2. This is so that we can simplify the advancement of the list in the next piece of code.
We’ll advance the list2 variable to make sure that list1 and list2 have the same number of remaining nodes (i.e. the same length).
We’ll compare the nodes to see if they point to the same node. We’ll do this so long as list1 and list2 are pointing to a node and they are not equal. If they are not equal, we advance nodes in the linked lists. Lastly, we’ll return the current node. If the nodes were equal, it will return the merge node. If the lists have been completely traversed, it will return None.
And we’re done! This problem has an O(n) time complexity, as we only need to traverse each list twice. This is technically O(2a + 2b), but this can just be shortened to O(n). The space complexity is O(1) constant, as no matter the list lengths, we’ll always have the same variables requiring no extra space.
This problem really teaches you about logical thinking in finding a solution. By thinking about how the two lists are related, we can easily determine a simple and effective solution.
Next week, we’ll either do more linked lists or stacks and queues — haven’t decided yet!
Check out the code on GitHub.
If you made it this far, thanks for the read. Have a wonderful week! ❤