Here are the Blind 75 Linked List Algorithm Summaries. Click to see the previous post on Interval Algorithms. A linked list is type of graph data structure with an additional constraint: the nodes form a chain by only having a maximum of one edge incoming and one outgoing. Since we can’t move backwards in this data structure or randomly access any node, we’ll use techniques like multiple pointers to solve these, ideally with one pass.

Reverse a Linked List

Given the head of a linked list, return it reversed.

Solution with O(n) time / O(1) space

You can reverse the list in-place by modifying the node direction.

Iterate through the list, saving the next and previous node. Set the current node to point to the previous node, and move to the saved next node.

Detect Cycle in a Linked List

Given the head of a linked list, determine if there is a cycle (where every node points to another node).

Solution with O(n) time / O(1) space

Iterate through the list with 2 pointers, the first pointer will look at nodes one at a time, and the second pointer will look two nodes ahead every iteration. If the second pointer ever encounters the same node as the first pointer, then the pointer must have cycled back, so the answer is that there is a cycle.

Merge Two Sorted Lists

Given two sorted linked lists, return a single sorted linked list by merging the two input lists.

Solution with O(n) time / O(n) space

Create a new result list.

Iterate through the inputs. While both inputs still have values, add the smaller value to the result list.

Then, add the rest of whichever list is left.

Merge K Sorted Lists

Given K sorted linked lists, return a single sorted linked list by merging all input lists.

Solution with O(n*k*log(n)) time and O(n) space where n is the average size of an input list and k is the number of lists

We will use a helper data structure, a priority queue, to do the heavy lifting on this one, which also determines the complexity above.

Add the head of all input lists to a priority queue. While the queue isn’t empty, poll it and put the value into a result list. Make sure to move the head of the polled list forward each time.

Remove Nth Node From End Of List

Given a linked list and an integer N, remove the node that is N nodes from the end of the list.

The first time I read this problem, I missed the whole point thinking that we needed to just remove the Nth node from the list, which would be simple using only one pointer.

Removing the Nth node from the end, though, will require a different solution for a linked list since we can only access nodes by following the head one at a time (no random access).

Solution with O(n) time and O(1) space, where in this case, n is the length of the list

Use two pointers, start and end.

Move the end pointer ahead N+1 nodes so that the start and end pointers are N+1 apart. They must be N+1 apart because remember that a linked list/graph node can’t remove itself, a node can only be removed by removing all reference to it from other nodes.

Iterate through, moving both pointers one at a time, until the end pointer is, well, at the end.

Remove the desired node by setting the next node of the start pointer to the next node of the next node.

Return the head of the input list.

Reorder List

Given a linked list, fold the list so that the end points of the list are at the beginning and the middle of the list is at the end (sorry that’s the best summary I could think of). Here’s what it looks like technically:

Input: Node1 → Node2 → Node3 → Node4 → Node5 → Node6

Output: Node1 → Node6 → Node2 → Node5 → Node3 → Node4

Solution with O(n) time / O(1) space

Use 2 pointers to find the middle node by moving the 2nd pointer twice as fast as the 1st pointer until the 2nd pointer is the the last or second to last node. The 1st pointer will be 1 before the middle.

Reverse the second half of the list using the method from the "Reverse a Linked List" problem.

Merge the reversed second half of the list into the first half similar to the "Merge Two Sorted Lists" problem, except you will alternate the lists evenly instead of picking by the value.

Check out the next post on Matrixes