Linked List Problems

I found a set of linked list coding problems I’d never seen before.

The document is titled Linked List Problems, written and copyright by Nick Parlante, dated 2002. Apparently Linked List Problems is part of the Stanford CS Education Library, which looks to date to around the end of the 20th Century.

Parlante’s reasons for studying linked lists and doing problems:

… these problems are a way to develop your ability with complex pointer algorithms. … the skills for complex pointer algorithms are very important, and linked lists are an excellent way to develop those skills.

Hillel Wayne has researched why doing linked list problems in interviews is traditional He thinks linked list problems got used to see if candidates could write working code in C.

Not exactly the same motivation, but Wayne is a consulting programmer, while Parlante is an academic and educator.

Critique of the problems

All told, this is a very good set of problems. The problems are in rough order of increasing difficulty, and cover a variety of techniques. Some of them are well known as interview or leetcode problems, some of them are new to me.

Write up

The document uses a lot of jargon: functions “take list heads”, and has the usual problems confusing node’s data values with the nodes themselves. For example, it represents example lists as [1 2 3], eliding all the “pointer” stuff, which is what Parlante wants readers to learn. It’s also the same sort of notation often used to present arrays. Experienced programmers can figure this out, but it’s supposed to be an educational document.

Parlante suggests test cases for only one problem. Long, hard experience leads me to try 0, 1, 2 and 5 length lists, or use 0, 1, 2 and 5 length arrays when writing algorithmic code. I found several problems with my initial cut at these problems by following my habitual practice of writing algorithms inside a simple testing harness, getting it to work the example, then trying 0-length input lists, or even and odd sized input list lengths.

Programming Style

Functions all have pointers-to-pointers-to-list-nodes formal arguments, and typically don’t return anything:

void Append(struct node** aRef, struct node** bRef)
void FrontBackSplit(struct node* source, struct node** frontRef, struct node** backRef)

First, I’m in favor of pass-by-value as much as possible. That style is less confusing. In general you cause fewer bugs by not modifying things out of sight. Maybe I’ve been affected by fiddling with lambda calculus and combinatory logic over the years, where an expression doesn’t have global effect. Functions ought to return some value(s), not set values in a reference argument.

I also object to writing struct node** aRef and not struct node **aRef, because the “**” part applies to aRef. If you wrote a variable declaration like:

struct node** aRef, bRef;

(which is entirely valid ANSI C) you’d get aRef of type struct node ** and bRef of type struct node. That’s not the obvious outcome. If you put the asterisk on the variable name, which is what it applies to, you reduce the cognitive load on readers of your code. They don’t have to remember that the “**” part applies only to the next variable, not all the variables declared in a list.

Notes on Some Problems

My solutions are a bit different than Parlante’s example solutions. I dislike special case if n == nil tests, so I work hard to avoid them.

Append() is remarkably simplified by the use of a dummy head node, a technique Parlante derides as a “slightly unusual technique”. I hadn’t seen dummy nodes used this way before, I learned something.

FrontBackSplit() isn’t nearly as hard as Parlante says. I looked at splitting linked lists using different methods in my mergesort investigations. Counting the list, then cutting it is just as hard as a rabbit/tortoise list walking approach, and requires more code. Using what Parlante calls “local references” (a “rarely used technique”) and I know as Linus Torvalds’ Good Taste, I was able to do the front/back split without special case code for lists less than 3 nodes in length.

This is also the only problem where Parlante suggests test cases.

ShuffleMerge() The word “ShuffleMerge” turns into “SuffleMerge” in the example solutions section. This document was clearly done with a lot of cut-n-paste back in 1999.

SortedIntersect() I haven’t seen this one before. It would actually be a good medium difficulty interview question. There’s probably more than one way to do it. Coding is required, so the interviewer would see coding style and design approach. Solutions to this problem in particular need to be tested, so a candidate could suggest them, or an interviewer could be prepared to ask to try test cases to see if the candidate can do debugging.

RemoveDuplicates() you can take advantage of the “increasing order” stipulation to make this just a list traversal with occasional node excision. If you did this in C, your code would be cluttered with memory deallocation.

RecursiveReverse() I’m not sure you can call a recursive linked list reversal “efficient”. A recursive algorithm uses a lot of stack, one stack frame per node in the list being reversed. I couldn’t be bothered to use the double-indirect head of list formal argument on this problem, otherwise I tried to stick to Parlante’s function signature. Taking advantage of Go’s multiple return values made the whole problem a lot simpler and clearer.