Tag Archives: linked lists

Linked List

Delete Node in a Linked List (Leetcode)

Another question from the archives. I was loathe to share this because it was an easy (or medium?) question at the time that I really hammered on but could not solve. The description makes it plain there’s not too many options on what to do, but having exhausted everything I could think of, I looked at the answer. It was not something I considered a good practical approach. Let’s discuss.

The Meta-Problem

You have a singly-linked list, and you have a pointer to a node, and you want to delete that node. The challenge is that, naively “blowing away” that object would invalidate the list: presumably there is some prefix that ends with the node you were given, and the node you were given may continue with some suffix.

So ideally you’d have a pointer to the node prior to the one you want to delete. Then you just do node.next = nodex.next.next, up to null-checks and the like. We lack that ability.

Vindication

Having returned to this question many years from now (and to be clear, my notes have the solution I ultimately got from the site), I feel vindicated. As of reading in June 2023, the following paragraph is included:

Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean: […]

That clarification was 100% missing in the version I read! I can’t objectively claim I would have gotten it with that clue, but saying delete and not meaning free-the-memory is a pretty weird construction.

So I would bet this question got a lot of feedback. Anyways, the solution is straightforward, it’s more an excuse to have a cute loop over linked lists.

class Solution:
    def deleteNode(self, node):
        prev = None
        while node.next is not None:
            node.val = node.next.val
            prev = node
            node = node.next
        prev.next = None
Introductory, Linked List

Middle of Linked List (Leetcode)

Another warm-up question from the archives.

The editorial solution, fast-and-slow-pointer, is very cute. I’m not sure how it’s preferable over separating the length (“fast”) calculation from the actual-find-calculation (“slow”). We’re doing the same traversals, but presumably with better locality?

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        l = 0
        n = head
        while n is not None:
            n = n.next
            l += 1

        n = head
        for i in range(l//2):
            n = n.next
        
        return n
Interview Questions, Linked List

Remove Linked List Elements (Leetcode 24)

Another removal-question. Another from the archive. Again the trickiness case is usually if the very-first or very-last element should be removed. I find this is another nice exercise giving the opportunity to think carefully about different cases happening inside a loop.

class Solution(object):
    def removeElements(self, head, val):
        # base case: remove from head until not equal to val
        while head is not None and head.val == val:
            head = head.next
        
        if head is None:
            return None
        
        t = head
        while t.next is not None:
            if t.next.val == val:
                t.next = t.next.next
            else:
                t = t.next
        
        return head
Interview Questions, Linked List

Add Two Numbers (Leetcode 21)

This is from the archives, when I’d take more notes. Let me take those insights and preserve them here.

Despite the name, this question is really about linked lists. I’ll assume you’ve read the question and understood it. Now, a few observations:

  1. We get to iterate through the list in the “nice” way: we can start adding digits immediately.
  2. Built into the question is the problem of “carries” — we’re adding things, but each node can only hold the values 0-9, and so if there’s overflow we have to carry that.
  3. This is a linked-list-merge-style question (see featured post here), so we should be mindful of the “end” of each of our two linked lists and how we should handle them. A moment’s thought also suggests that the carry value can also play a role here!
  4. No negative numbers! The natural approach doesn’t suggest we’d introduce an erroneous leading zero or anything either. So it doesn’t seem there’s anything too tricky here.

Some insights:

  1. We can treat the carry value as a “virtual” node: this tightens up our iterations and puts everything into one loop.
  2. The approach I took was to create a new, third list. Another option (in practice; I assume the autograder would accept this too) would be to make this transformation destructive of one or both lists.
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* lastDigit = nullptr;
        ListNode* result = nullptr;
        bool carry = false;
        
        while (l1 || l2 || carry) {
            auto l1val = l1 ? l1->val : 0;
            auto l2val = l2 ? l2->val : 0;
            auto nextVal = l1val + l2val;
            
            if (carry) {
                nextVal++;
                carry = false;
            }
            
            if (nextVal > 9) {
                nextVal -= 10;
                carry = true;
                // assert(nextVal < 10 && nextVal >= 0)
            }
            
            if (!result) {
                result = new ListNode(nextVal);
                lastDigit = result;
            } else {
                lastDigit->next = new ListNode(nextVal);
                lastDigit = lastDigit->next;
            }
            
            if (l1) { l1 = l1->next; }
            if (l2) { l2 = l2->next; }
        }
        
        return result;
    }
};

I think this is a nice interview question.

Interview Questions, Linked List

Remove Duplicates from Sorted LL (Leetcode 11)

Leave a comment

There is definitely a pattern! Sorted array, and previously move zeros. Well this has no relation to the remove-zeros, but it’s interesting….

This suggests an interesting lesson as well, three variations on a theme. That’s why I’m doing these things.

class Solution(object):
    def deleteDuplicates(self, head):
        if head is None:
            return head
        curr = head
        while curr is not None and curr.next is not None:
            while curr.next is not None and curr.val == curr.next.val:
                curr.next = curr.next.next
            curr = curr.next
        return head

I bet there’s a nicer way of writing that loop. It’s interesting that this logic “feels” neater to me (especially if my suspicion of a nicer way of writing that loop bears out.)

Nested loops with linked lists! Neat.

Interview Questions, Linked List

Merge Sorted Lists (Leetcode 2)

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.