5 Chapter 5 Solutions¶

Solution to Challenge 1¶

A straightforward way to solve this problem is to use recursion. Since recursion allows you to build a call stack, you just need to call the print statements as the call stack unwinds.

Add the following helper function to your project:

void printNodesRecursively<T>(Node<T>? node) {
  // 1
  if (node == null) return;

  // 2
  printNodesRecursively(node.next);

  // 3
  print(node.value);
}

You start off with the base case: the condition for terminating the recursion. If node is null, then it means you’ve reached the end of the list.
This is your recursive call, calling the same function with the next node.
Where you add the print statement will determine whether you print the list in reverse order or not. Any code that comes after the recursive call is called only after the base case triggers, that is, after the recursive function hits the end of the list. As the recursive statements unravel, the node data gets printed out.

Finally, you need to call the helper method from a printInReverse function:

void printListInReverse<E>(LinkedList<E> list) {
  printNodesRecursively(list.head);
}

To test it out, write the following in your main function:

var list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);

print('Original list: $list');
print("Printing in reverse:");
printListInReverse(list);

You should see the following output:

Original list: 1 -> 2 -> 3
Printing in reverse:
3
2
1

The time complexity of this algorithm is O(n) since you have to traverse each node of the list. The space complexity is likewise O(n) since you implicitly use the function call stack to process each element.

Solution to Challenge 2¶

One solution is to have two references traverse down the nodes of the list, where one is twice as fast as the other. Once the faster reference reaches the end, the slower reference will be in the middle. Update the function to the following:

Node<E>? getMiddle<E>(LinkedList<E> list) {
  var slow = list.head;
  var fast = list.head;

  while (fast?.next != null) {
    fast = fast?.next?.next;
    slow = slow?.next;
  }

  return slow;
}

In the while loop, fast checks the next two nodes while slow only gets one. This is known as the runner’s technique.

Write the following in your main function:

var list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);
print(list);

final middleNode = getMiddle(list);
print('Middle: ${middleNode?.value}');

You should see the following output:

1 -> 2 -> 3
Middle: 2

The time complexity of this algorithm is O(n) since you traversed the list in a single pass. The runner’s technique helps solve a variety of problems associated with a linked list.

Solution to Challenge 3¶

To reverse a linked list, you must visit each node and update the next reference to point in the other direction. This can be a tricky task since you’ll need to manage multiple references to multiple nodes.

The Easy Way¶

You can trivially reverse a list by using the push method along with a new temporary list. Either add a reverse method to LinkedList or create an extension like so:

extension ReversibleLinkedList<E> on LinkedList<E> {
  void reverse() {
    final tempList = LinkedList<E>();
    for (final value in this) {
      tempList.push(value);
    }
    head = tempList.head;
  }
}

You first start by pushing the current values in your list to a new temporary list. This will create a list in reverse order. After that point the head of the list to the reversed nodes.

O(n) time complexity, short and sweet!

But Wait…¶

Although O(n) is the optimal time complexity for reversing a list, there’s a significant resource cost in the previous solution. As it is now, reverse will have to allocate new nodes for each push method on the temporary list. You can avoid using the temporary list entirely and reverse the list by manipulating the next pointers of each node. The code ends up being more complicated, but you reap considerable benefits in terms of performance.

Replace the reverse method with the following:

void reverse() {
  tail = head;
  var previous = head;
  var current = head?.next;
  previous?.next = null;

  // more to come...
}

You begin by assigning head to tail. Next, you create two references — previous and current — to keep track of traversal. The strategy is fairly straightforward: each node points to the next node down the list. You’ll traverse the list and make each node point to the previous node instead:

prevcurrentprevcurrentthe rest of the list

As you can see from the diagram, it gets a little tricky. By pointing current to previous, you’ve lost the link to the rest of the list. Therefore, you’ll need to manage a third pointer. Add the following at the bottom of the reverse method:

while (current != null) {
  final next = current.next;
  current.next = previous;
  previous = current;
  current = next;
}

Each time you perform the reversal, you create a new reference to the next node. After every reversal procedure, you move the two pointers to the next two nodes.

Once you’ve finished reversing all the pointers, you’ll set the head to the last node of this list. Add the following at the end of the reverse method:

head = previous;

Try it Out!¶

Test the reverse method by writing the following in main:

var list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(1);

print('Original list: $list');
list.reverse();
print('Reversed list: $list');

You should see the following output:

Original list: 1 -> 2 -> 3
Reversed list: 3 -> 2 -> 1

The time complexity of your new reverse method is still O(n), the same as the trivial implementation discussed earlier. However, you didn’t need to use a temporary list or allocate any new Node objects, which significantly improves the performance of this algorithm.

Solution to Challenge 4¶

This solution traverses down the list, removing all nodes that match the element you want to remove. Each time you perform a removal, you need to reconnect the predecessor node with the successor node. While this can get complicated, it’s well worth it to practice this technique. Many data structures and algorithms will rely on clever uses of pointer arithmetic.

There are a few cases you need to consider. The first case to consider is when the head of the list contains the value that you want to remove.

Trimming the Head¶

Suppose you want to remove 1 from the following list:

head112

You’d want your new head to point to 2.

Create an extension on LinkedList and add a removeAll method to it:

extension RemovableLinkedList<E> on LinkedList {
  void removeAll(E value) {

  }
}

Then add the following while loop to removeAll:

while (head != null && head!.value == value) {
  head = head!.next;
}

Since it’s possible to have a sequence of nodes with the same value, the while loop ensures that you remove them all. The loop will finish if you get to the end of the list or when the value is different.

Unlinking the Nodes¶

Like many of the algorithms associated with linked lists, you’ll leverage your pointer arithmetic skills to unlink the nodes. Write the following at the bottom of removeAll:

var previous = head;
var current = head?.next;
while (current != null) {
  if (current.value == value) {
    previous?.next = current.next;
    current = previous?.next;
    continue;
  }
  // more to come
}

You need to traverse the list using two pointers: previous and next. The if block will trigger if it’s necessary to remove a node.

You modify the list so that you bypass the node you don’t want:

prevprevcurrentcurrent

Keep Traveling…¶

Can you tell what’s missing? As it is right now, the while loop may never terminate. You need to move the previous and current pointers along. Write the following at the bottom of the while loop, replacing the // more to come comment:

previous = current;
current = current.next;

Finally, you’ll update the tail of the linked list. This is necessary when the original tail is a node containing the value you wanted to remove. Add the following to the end of removeAll:

tail = previous;

And that’s it for the implementation!

Try it Out!¶

Write the following in main:

var list = LinkedList<int>();
list.push(3);
list.push(2);
list.push(2);
list.push(1);
list.push(1);

list.removeAll(3);
print(list);

You should see the following output:

1 -> 1 -> 2 -> 2

This algorithm has a time complexity of O(n) since you need to go through all the elements.