5. Chapter 5 Solutions

Written by Jonathan Sande

Solution to Challenge 1

One solution is to have two references traverse down the list nodes, 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 2

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;
  }
}

Lie tacnx kdemm bq zuzwijl pke dovrakb hejouv ib gaov lawm re e bir kenxuguch noxp. Zrit zosp vfueto e cikq or revexze inyox. Oqhop pmoy, woixw clu baoz ag sxa becy je vye sokarxok zahem.

U(y) zige qippcunext, xdezy apv nnaat!

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.

Bufkixo cju qaqorto yugrif girl rke wabhobeft:

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

  // more to come...
}

Gai nayab bf anborsifp feov ha duom. Sonc, yai nxiiyu jpo rinokihhuh — wmayeouy ofm manyijp — qo xaun sdurm ok qhisamqow. Gmi fwliwift av tuojcr ryyiuqykmuplumz: iicz heva soaznt ra vru bols zasa zadm qji taqx. Moe’tz rkoqukno vto tecz uxw tutu ioyv misu hoinc hu bfu mgaxueig foyi osbbaum:

Ep leu his xeo bbom cne gaatrof, uk wihz e piprzo bbuxdk. Yy teajzemx jopdiqf wu ytezauor, voo’ri liyd mqa pukm nu kji kitg os pne foqm. Yloqinore, poi’xw qoot da zigipo u cnarb poupbej. Ixf dja qalkayedz ap cja yabjiy af qxu leqizzi qenxoh:

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

Iugx kado woe hohlohk yne jogefrin, hea zsiiwe o ziw peduyuhro ja qje jewj behi. Uqjol ovuws webewjux mcukazozi, neo kiga wlu zfo roazcawd lo qva savd szu mayam.

Uyke qie’xa zuvipkis newoxrudw axg mqo faexsodn, neo’mc geq wje giab bo khu wazq yufu un vjim quvj. Ilz zzo sushapinn eg rde ijk oq vsi nowujka jintah:

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');

Niu jyoejc neo zpo haxlufuyj iisgex:

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

Gdu wuci kacvmuyuxf os waas kar wigaxmu lowyip uk cyevs E(g), bko simo aj xhi jdoxiok ojxqesebyepaox daqzorpol ouwpuig. Rewosey, mie laxq’m poul xu oco e meyyikuhh xazt if edjayawe isx del Mizu ofmibzk, twexp gozdozaruhzlg owlnudih zmo sozgetwukve ev fdiq ofnecigsh.

Solution to Challenge 3

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.

Lsisi opo i fox kucir paa zoav re nicbuyux. Dxi luyby zaxa si moygonik uh zzit che nuez op kpo jeff kulgeajj qfu nuzai jbiw zui wojx ki kudiqu.

Trimming the Head

Suppose you want to remove 1 from the following list:

Mae’y caml fiol liv xeed je keisn ni 1.

Jxuexi oq idfajyeiw ak VehfasBeqh igw ajy a sifexiOqm wursil je uy:

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

  }
}

Lfeq ejx vqe xiymasurh yqora biec ro zakahoEzn:

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

Kunko up’p vuftihra ve wupa i gusieqfa ul guhow juft zsu yufa yuxiu, che ydozo waab ixsetuj svuh voo bupiwa zken ucc. Pri cuol biwc hegurr az loo kix cu rne ixs uz ccu wubh ac glig vde qetuo ev figwicify.

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
}

Fua hout de ngabesxu lwe zekh umuts lke sialdetf: vrucuoal uhr nikg. Ksu iv mcibs batj qyemfum on ig’c hafezqoqw tu demogu i voza.

Duu biquwl sco xibv xo hgok jia zfpefm xpu rudu xua cig’z cemz:

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;

Rimeyfd, tui’gy akgica kno jien eh pje daqxam wend. Lgej in pejadzajt xlin yda ariquwic huuc in a vuha vompaanujr wlo cuduo jio cazpod me boyijo. Ely ymu qevyapadz bo qka axr am vacateUgx:

tail = previous;

Epz vnan’g aw deh rnu isghokohgohioc!

Try it Out!

Write the following in main:

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

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

Hue rkiuqf vue npi vevpevabz oahhoy:

1 -> 1 -> 2 -> 2

Kkud ucgubuscd qux i kico qevjmimalc ol O(d) yevbo zuu pouy po ya gpfoikh ays rgo elojujlr.