Xuanyi Fu Blog
0%

Linked List Made Easy

Posted on Edited on
Symbols count in article: 7.4k

Tackle down most of linked list problems easily with basic concepts from functional programming.

Think Recursively

Linked List is Defined Recursively

A linked list is either:

  • An empty list.
  • A node that contains a value and a reference to a linked list.

The definition of linked list uses the definition itself, making it a recursive data structure.

Take a closer look at the single-linked list definition that you could see on every linked list problem in LeetCode. (C++ ver.)

1
2
3
4
5
6
7
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
  • int val; is the value that a node contains.
  • ListNode* refers to a linked list that a node holds.
  • nullptr is the empty list.

Length As an Example

How would you get the length of a linked list?

Iteratively

  • Start with a pointer points to the head and a counter set as 0.
  • Make the pointer move along the list and increase the counter at the same time.
  • When the pointer points to nullptr, we stop here and return the result.
1
2
3
4
5
6
7
8
int Length(ListNode* head) {
    auto len = 0;
    while(head) {
        ++len;
        head = head->next;
    }
    return len;
}

Iteratively, we consider the linked list as a whole. It is a sequence of nodes that we can be iterative on. The sequence is marked with head as begin and next == nullptr as the end.

1
2
3
4
5
┌────┐ ┌►┌────┐ ┌►┌────┐ ┌►┌────┐ ┌►┌───────┐
│val │ │ │val │ │ │val │ │ │val │ │ │val    │
├────┤ │ ├────┤ │ ├────┤ │ ├────┤ │ ├───────┤
│next├─┘ │next├─┘ │next├─┘ │next├─┘ │nullptr│
└────┘   └────┘   └────┘   └────┘   └───────┘

Recursively

To think recursively, we have to change our way of thinking. Take these three points in mind, and you could be a recursive guy.

  • Stop considering the list as a sequence that you can iterate on. You should refrain from making the pointer move forward and backward in a loop.
  • Stop thinking about the list as a whole. Narrow your focus to the current list. It could be either
    • an empty list.
    • a node with a value and the list it holds a reference to.
  • While implementing a recursive function, assuming it works as expected when calling it recursively. Do not try to get to the bottom of the recursive stack to find out why the recursion works. Function is born to be a way of black-box abstraction.

Let us implement Length recursively.

We first narrow our focus on the current node and the list it holds references to.

  • If the current list is empty, its length is 0.
  • If the current list is not empty, we should consider how to get the length from the current node and the list it holds the reference to.
    • the current node contribute 1 to the length of the list
    • We could get the length of the list it holds the reference to by calling Length recursively on it. At this point, the function Length has been not finished yet. However, persuade yourself into thinking that the Length you are calling is a pretty pretty function that works just as you expected.
    • We add them together, and that is our result.
1
2
3
4
5
6
int Length(ListNode* head) {
    if(!head) {
        return 0;
    }
    return 1 + Length(head->next);
}

Nice, we can think recursively now!

Build our Util Library

Basic Building Blocks

IMMUTABILITY is Not Our Concern!

Foldr

How do we get the length of our list recursively? 

1
2
3
4
5
6
int Length(ListNode* head) {
    if(!head) {
        return 0;
    }
    return 1 + Length(head->next);
}

How do we get the product of values in list nodes recursively?

1
2
3
4
5
6
7
int Mul(ListNode* head) {
    if(!head) {
        return 1;
    }

    return head->val * Mul(head->next);
}

Length and Mul are similar, aren’t they? To find the common part of them, let us rewrite them with Add1 and Mul2 to avoid using infix operators operator+ and operator*.

1
2
3
4
5
6
7
8
9
10
int Add1(ListNode*, int len) {
    return 1 + len;
}

int Length(ListNode* head) {
    if(!head) {
        return 0;
    }
    return Add1(head, Length(head->next));
}

(Notice that the first argument ListNode* is an unused variable.)

1
2
3
4
5
6
7
8
9
10
int Mul2(ListNode* x, int product) {
    return x->val * product;
}

int Mul(ListNode* head) {
    if(!head) {
        return 1;
    }
    return Mul2(head->val, Mul(head->next));
}

They are similar because

  • Length and Mul both have an initial value, 0 and 1 respectively, returned when the list is empty.
  • They both call the function with two parameters: the node itself and the recursive result of the rest of the list.
    • They both return the result of the function.

The function calling trees for them are like

1
2
3
4
5
add1(t0, 
    add1(t1, 
        add1(t2, ..., 
            add1(tN, 0
) ... )))
1
2
3
4
5
Mul2(t0, 
    Mul2(t1, 
        Mul2(t2, ..., 
            Mul2(tN, 1
) ... )))

Let’s take the list [1,2,3,4,5] as an example. we are computing the following 

1
(1 * (2 * (3 * (4 * (5 * 1)))))

Let’s make it more general. Assume the value held in the list node has type T. We have a function f that accepts two parameters of type ListNode* and U and returns a value of type U. Given an initial value i of type U, we want to compute 

1
2
3
4
5
6
7
8
f(t0, 
    f(t1, 
        f(t2, 
            f(t3, 
                ... ,
                    f(t(N-1), i)

) ... ))))

This operation on the list is always called Foldr for “fold right.”

For Length, i is 0. The function f is add1.
For Mul, i is 1. The function f is Mul2.

Now, Let us implement Foldr

1
2
3
4
5
6
7
8
template<typename Func, typename Init>
Init Foldr(Func func, Init init, ListNode* head) {
    if(!head) {
        return init;
    }

    return func(head, Foldr(func, init, head->next));
}

It is similar to Length and Mul, right? Now, we could rewrite Length and Mul with Foldr.

1
2
3
4
5
6
7
8
9
10
11
int Length(ListNode* head) {
    return Foldr([](ListNode*, int len){
        return len + 1;
    }, 0, head);
}

int Mul(ListNode* head) {
    return Foldr([](ListNode* x, int product){
        return x->val * product;
    }, 1, head);
}

Foldl

Foldl is similar to Foldr. However, Foldl benefits from recursion, which be optimized by most compilers.

Assume the value held in the list node has type T. We have a function f that accepts two parameters of type ListNode* and U and returns a value of type U. Given an initial value i' of typeU,Foldl` computes

1
f( ... f(f(f(init, t0), t1), t2),t3) ... , t(N-1))

Another difference between Foldr and Foldl is using the initial value. Foldr combines the initial value with the last element. However, Foldl` combines it with the first element of the list.

To make it safe to modify ListNode::next while calling Foldl, we should copy the head->next before we call func.

1
2
3
4
5
6
7
8
template<typename Func, typename Init>
Init Foldl(Func func, Init init, ListNode* head) {
    if(!head) {
        return init;
    }
    auto next = head->next;
    return Foldl(func, func(head, init), next);
}

SplitAt

SplitAt(n, head) splits a list into two. All nodes before the n-index node go to the first half. The others go to the second half. For example:

1
2
3
4
5
SplitAt(-1, [1,2,3,4,5]) -->  ([]         , [1,2,3,4,5])
SplitAt(0 , [1,2,3,4,5]) -->  ([]         , [1,2,3,4,5])
SplitAt(1 , [1,2,3,4,5]) -->  ([1]        , [2,3,4,5]  )
SplitAt(2 , [1,2,3,4,5]) -->  ([1,2]      , [3,4,5]    )
SplitAt(5 , [1,2,3,4,5]) -->  ([1,2,3,4,5], []         )

Splitting at an index equal to zero or less than zero does not split anything. The original list will always go to the second half of the result. The first half of the result will be empty.

If we split an empty list, we get two empty lists in return.

Let’s split a non-empty list head at index n > 0 recursively. Look what we have here!

  • head, the node
  • head->next, the rest of the list
  • SplitAt, the function

The nth node in the current list is the (n-1)th node in the rest of the list. Take the following drawing as an example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
head
 │       │
 │       │
┌▼┌─┬─┬─┐▼┌──────────────┬─┐
│0│1│2│3│4│ . . .        │ │
└─┴─┴─┴─┴─┴──────────────┴─┘
   ▲
   │     │
   ▼     │
  ┌─┬─┬─┐▼┌──────────────┬─┐
  │0│1│2│3│ . . .        │ │
  └▲└─┴─┴─┴──────────────┴─┘
   │
   │
  head->next

Therefore, we could call SplitAt(n - 1, head->next) to split the rest of the list. The result of SplitAt(n - 1, head->next) will be a pair of lists. Finally, we prepend head on the first half of the list. Then, we get a recursive SplitAt!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
using ListNodePair = std::pair<ListNode*, ListNode*>;
ListNodePair SplitAt(int n, ListNode* head) {
    if(n <= 0) {
        return ListNodePair{nullptr, head};
    }

    if(!head) {
        return ListNodePair{nullptr, nullptr};
    }

    auto [p1, p2] = SplitAt(n - 1, head->next);
    head->next = p1;
    return {head, p2};
}

Append

  • Append an empty list onto another list does nothing.
  • Append a list onto an empty list does nothing.
  • Append a list with more than one node is append the current head to the head of the Append(head->next, r).
1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* Append(ListNode* l, ListNode* r) {
    if(!l) {
        return r;
    }

    if(!r) {
        return l;
    }

    // l && r && l->next
    l->next = Append(l->next, r);
    return l;
}

ZipWith

ZipWith is like Foldr but for folding two lists at the same time. The caller is responsible for deallocating the memory. Unlike most implementations, this ZipWith continues on the longer list when the shorter list is depleted. When this is happening, the func will be called with the shorter list node filled with nullptr.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename Func>
ListNode* ZipWith(Func func, ListNode* l, ListNode* r) {

  if(!l && !r) {
    return nullptr;
  }

  if(!l) {
    return new ListNode{func(l, r), ZipWith(func, l, r->next)};
  }
  
  if(!r) {
    return new ListNode{func(l, r), ZipWith(func, l->next, r)};
  }
  
  return new ListNode{func(l, r), ZipWith(func, l->next, r->next)};
}

Example: 

1
2
3
4
5
6
7
8
9
10
// list1 : [1,2,3,4]
// list2 : [5,6,7,8,9]

auto* zipResult = ZipWith([](ListNode* l, ListNode* r){
    auto lv = l ? l->val : 1;
    auto rv = r ? r->val : 1;
    return lv * rv;
}, list1, list2);

// zipResult : [5,12,21,32,9]

Utils

Length

We could build Length with Foldl.

1
2
3
4
5
int Length(ListNode* head) {
    return Foldl([](ListNode* x, int len){
        return len + 1;
    }, 0, head);
}

Reverse

We could reverse the list by prepending all nodes we visit in Foldl to the initial value nullptr.

1
2
3
4
5
6
ListNode* Reverse(ListNode* head) {
    return Foldl([](ListNode* x, ListNode* result){
        x->next = result;
        return x;
    }, static_cast<ListNode*>(nullptr), head);
}

Why do we not prefer Foldr? Foldr visits all nodes in the list in reverse order, which means we have to Append the node we visit at the end of the result. Remember, we are dealing with a linked list. Appending a node at the end of a singly-linked list requires traversing to the end of the list. Traversing the whole list is not fast.

1
2
3
4
5
6
7
8
ListNode* Reverse(ListNode* head) {
    return Foldr([](ListNode* x, ListNode* result){
        x->next = nullptr;
        // this could be really slow: O(N)
        Append(result, x);
        return result;
    }, static_cast<ListNode*>(nullptr), head);
}

Filter

Just Foldr. Built a new list with nodes of interest.

1
2
3
4
5
6
7
8
9
10
template<typename UnaryFunction>
ListNode* Filter(UnaryFunction pred, ListNode* head) {
    return Foldr([pred](ListNode* x, ListNode* result) {
        if(pred(x)) {
            x->next = result;
            return x;
        }
        return result;
    }, static_cast<ListNode*>(nullptr), head);
}

Partition

Just Foldr. Build a new pair of lists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
using ListNodePair = std::pair<ListNode*, ListNode*>;

template<typename UnaryFunction>
ListNodePair Partition(UnaryFunction pred, ListNode* head) {
    return Foldr([pred](ListNode* x, ListNodePair result) {
        if(pred(x)) {
            x->next = result.first;
            return {x, result.second};
        }

        x->next = result.second;
        return {result.first, x};
    }, ListNodePair{nullptr, nullptr}, head);
}

Linked List Made Easy

Equip yourself with the library we have just built. Tackle down linked list challenging problems in no time.

Delete, Insert Nodes in a Linked List

LC2095 - Delete the Middle Node of a Linked List

LC2095 Delete the Middle Node of a Linked List

  • Get the length of the list
  • Split the list at length / 2
  • Split the second half of previous result at 1
  • Append them together
1
2
3
4
5
ListNode* deleteMiddle(ListNode* head) {
    auto [p1, p2] = SplitAt(Length(head) / 2, head);
    std::tie(std::ignore, p2) = SplitAt(1, p2);
    return Append(p1, p2);
}

LC1669 - Merge In Between Linked Lists

SplitAt twice, Append twice

1
2
3
4
5
ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
    auto [p1, p2] = SplitAt(a, list1);
    std::tie(std::ignore, p2) = SplitAt(b - a + 1, p2);
    return Append(p1, Append(list2, p2));
}

Reverse a Linked List

LC25 - Reverse Nodes in k-Group

LC25 Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

Solving this problem is just translating the sentence into our util library’s language.

Reversing an empty linked list with whatever k provided will give us an empty linked list.

1
2
3
4
5
6
7
ListNode* reverseKGroupRec(int k, ListNode* head) {
  if(!head) { 
      return head; 
  }

  // ...
}

If the number of nodes is not a multiple of k, then left-out nodes, in the end, should remain as it is.

This statement indicates that if the length of a list is less than k, it should remain untouched.

1
2
3
4
5
6
7
ListNode* reverseKGroupRec(int k, ListNode* head) {
  if(!head || Length(head) < k) { 
      return head; 
  }

  // ...
}

reverse the nodes of the list k at a time

If the length of a list is no less than k, “k at a time” requires us to SplitAt k.

1
2
3
4
5
6
7
8
9
ListNode* reverseKGroupRec(int k, ListNode* head) {
  if(!head || Length(head) < k) { 
      return head; 
  }

  auto [firstHalf, secondHalf] = SplitAt(k, head);

  // ...
}

Then we Reverse the firstHalf.

1
2
3
4
5
6
7
8
9
10
ListNode* reverseKGroupRec(int k, ListNode* head) {
  if(!head || Length(head) < k) { 
      return head; 
  }

  auto [firstHalf, secondHalf] = SplitAt(k, head);
  firstHalf = Reverse(firstHalf);

  // ...
}

We do recursion on the secondHalf and Append the firstHalf to the result of the recursion.

1
2
3
4
5
6
7
8
9
10
11
ListNode* reverseKGroupRec(int k, ListNode* head) {
  if(!head || Length(head) < k) { 
      return head; 
  }

  auto [firstHalf, secondHalf] = SplitAt(k, head);
  firstHalf = Reverse(firstHalf);
  secondHalf = reverseKGroupRec(k, secondHalf);

  return Append(firstHalf, secondHalf);
}

Let’s refactor the code to eliminate some unnecessary assignments.

1
2
3
4
5
ListNode* reverseKGroupRec(int k, ListNode* head) {
  if(!head || Length(head) < k) { return head; }
  auto [firstHalf, secondHalf] = SplitAt(k, head);
  return Append(Reverse(firstHalf), reverseKGroupRec(k, secondHalf));
}

Thanks to the Util Library and Recursion, this complicated problem has been solved with only three lines of code!

Reorder a Linked List

LC143 - Reorder List

LC143 Reorder List

You are given the head of a singly-linked list. The list can be represented as:

1
L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

1
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

Four easy steps.

  1. Get the length of the list.
  2. Split the list at the half.
  3. Reverse the second half of the list.
  4. Interweave the list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* Interweave(ListNode* l, ListNode* r) {
  if(!l) {
    return r;
  }
  
  if(!r) {
    return l;
  }
  
  // l && r
  l->next = Interweave(r, l->next);
  return l;
}

void reorderList(ListNode* head) {
    auto [p1, p2] = SplitAt(Length(head) / 2, head);
    Interweave(p1, Reverse(p2));
}

Big Integer as Linked List

LC369 Plus One Linked List

LC369 Plus One Linked List

  • Foldr on the list with initial value 1.
  • If Foldr returns a 1, we have to create a new node as the new most significant digit.
1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* plusOne(ListNode* head) {
    const auto carry = Foldr([](ListNode* head, int carry){
        const auto val = head->val + carry;
        head->val = val % 10;
        return val / 10;
    }, 1, head);
    
    if(carry) {
        head = new ListNode{1, head};
    }
    
    return head;
}

LC2 Add Two Numbers

LC2 Add Two Numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int Carry(ListNode* head) {
  return Foldl([](ListNode* x, int carry){
    auto v = x->val + carry;
    x->val = v % 10;    
    return v / 10;
  }, 0, head);
}

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

    auto* sum = ZipWith([](auto* lhs, auto* rhs){
        auto l = lhs ? lhs->val : 0;
        auto r = rhs ? rhs->val : 0;
        return l + r;
    }, l1, l2);

    auto carry = Carry(sum);
    if(carry) {
        Append(sum, new ListNode{1, nullptr});
    }
    return sum;
}

LC445 Add Two Numbers II

LC445 Add Two Numbers II

LC445 is almost the same as LC2 Add Two Numbers except that we have to reverse the two number lists at first.

1
2
3
4
5
6
class Solution {
public:
    ListNode* addTwoNumbers2(ListNode* l1, ListNode* l2) {
        return Reverse(addTwoNumbers(Reverse(l1), Reverse(l2)));
    }
};