This one’s a classic. Given two sorted lists, merge them into a single sorted list. My “go-to” interview question is a variation of this. While linked lists and pointers may not come up every day, this has an interesting loop that solves a problem not-too-different from ones that come up in real life, collating two different sources of information.

There are also plenty of edge cases to worry about, even while (I think, for people with a college background) the problem is familiar enough to not be overwhelming. Some highlights:

1. People often forget the final block, where we deal with the “stragglers” in the case that l1 and l2 weren’t close to the same length.
2. People often end up getting very concerned and confused about the body of the main loop — merging is a tricky operation, I don’t blame them. I don’t expect a polished response, but it is a measure of how confidently people can reason about loop invariants.
3. Maybe loop invariants seems like a fancy and intimidating term, but we often do that informally: what’s true “on every iteration of the loop”? It’s a powerful question.

Behind-the-scenes, this presents an opportunity to really reason about pointers and references. A natural sequel question is an “intersection” (rather than union) sort of problem. The problem can be made simpler, for some people, by merging two arrays, and forgetting memory concerns for the time being.

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        
        rhead = None
        if l1.val < l2.val:
            rhead = l1
            l1 = l1.next
        else:
            rhead = l2
            l2 = l2.next
        r = rhead
        
        while l1 is not None and l2 is not None:
            if l1.val < l2.val:
                r.next = l1
                r = r.next
                l1 = l1.next
            else:
                r.next = l2
                r = r.next
                l2 = l2.next
        
        if l1 is not None:
            r.next = l1
        else:
            r.next = l2
        
        return rhead

You can find all of the linked list problems solved on this site here.