Category Archives: Linked List

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

Reverse a Linked List (Leetcode)

It’s time. It’s obvious I have a lot of linked questions, and here’s the classic. At least when I was an intern way-back-when, this was a cliche “overdone and inappropriate interview question”. It’s a nice exercise on thinking about linked lists, but unless your job requires it (my first job did!) I understand it feels a bit esoteric. Still, I like it.

Iterative Solution

class Solution(object):
    def reverseList(self, head):
        tail = None
        while head:
            n = head
            head = head.next
            n.next = tail
            tail = n
        return tail

Recursive Solution

class Solution(object):
    def reverseList(self, head):
        if head is None:
            return None
        if head.next is None:
            return head
        newTail = head
        head = head.next
        newTail.next = None
        res = self.reverseList(head)
        head.next = newTail
        return res

Discussion

I’m open to being wrong, but it seems that the iterative solution is nicer than the recursive one? Some of the pointer “faith”, in particular that head points to the tail of the reversed sub-list (penultimate line), is a bit much. With pointers that’d be a lot clearer I think, but Python’s references make it a bit fuzzier for me.

If anything, I think the reasoning about how the iterative solution works is very recursive-feeling. Or at least a nice application of loop invariants.

This question covers a lot! More linked list questions are here.

Interview Questions, Linked List

Split Linked List In Parts (Leetcode)

This question feels a bit contrived, but a way to explore a lot of challenges with linked lists. I have an answer to this in my archive.

So, full disclosure: most of my archive is actually in C++, rather than the more approachable Python or (occasionally, for my students) Javascript. I think I do have a few earlier solutions in C++, but this is the first “big” one, I guess? Previously I’ve also been translating my archive, but as my external obligations are increasing I have to drop some features. So this is in C++. Also from the archive: a lot of my notes were intentionally embedded in comments.

class Solution {
public:
    // it seems we need to know the length, to begin with.
    // and then we do an interesting partition sort of algorithm.
    // the value of the LL nodes play no part in this?
    // Sure...
    int len(ListNode* r) {
        int l = 0;
        while (r) {
            l++;
            r = r->next;
        }
        return l;
    }
    // OK, and then we divide things into K.
    // Ah that things differ by less than 1 is sort of an interesting constraint.
    // So if k > l, that's sort of easy: we know we need length 1.
    // if k < l < 2k, then we know we'll have a few length-2, and the rest length 1.
    // So this suggests some kind of modulo. k > 0, so that's safe.
    // l / k is the length of the shorter lists.
    // l % k is how many lists need one more.
    // This feels like an obsfucated remainder check. But actually it's OK. I kind of like
    // this partition problem.
    
    ListNode* peel(ListNode** root, int l) {
        // forgot a deref!
        if (!(*root)) return nullptr; // assert l == 1?
        ListNode* p = *root;
        ListNode* t = *root;
        // Here I'm being a bit risky. Not sure if there's a weird case
        // where if we improperly peel we'll null-deref. I think if everything
        // goes right we'll only ever be "off by one", which is effectively
        // captured by our basecase there.
        //
        // In other words, this is not a very robust peel! Relies on qualities
        // of the list guaranteed by the caller.
        for (int i = 0; i < l-1; ++i) {
            t = t->next;
        }
        *root = t->next;
        t->next = nullptr;
        return p;
    }
    
    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        const int l = len(root);
        int shortLength = l / k;
        int listsWithExtras = l % k;
        // next up: helper function "peel";
        vector<ListNode*> result;
        ListNode* r = root;
        for (int i = 0; i < k; ++i) {
            int n = shortLength;
            if (i < listsWithExtras) {
                n++;
            }
            result.push_back(peel(&r, n));
        }
        return result;
    }
};

Notes

A few notable things:

  • The len helper, it seems to be required? It’s unfortunate that we can’t do this online.
  • I’m having second thoughts about my implementation of “peel”. I think I can avoid the pointer-to-pointer, though for C that’s not a huge deal. Maybe inlining the function would make that clearer.
  • You can see my careful-ish reasoning about how to calculate each peel length, I think that’s an interesting comment.

As always, all linked list things are collected here.

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

Flatten a Doubly-Linked List (Leetcode 8)

Leave a comment

Isn’t this basically the same as the last one? Instead of left and right it’s “child” and “next”. The doubly-linked stitching is a bit different, but nothing major. Interesting contrast.

class Solution(object):
    def flatten(self, head):
        if head is None:
            return None
        if head.child is None:
            self.flatten(head.next)
            return head
        flatChild = self.flatten(head.child)
        head.child = None

        childEnd = flatChild
        while childEnd.next != None:
            childEnd = childEnd.next
        
        
        oldNext = head.next
        if oldNext:
            oldNext.prev = childEnd
        childEnd.next = oldNext

        flatChild.prev = head
        head.next = flatChild
        
        return head
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.