5. Chapter 5 Solutions

Written by Kelvin Lau & Jonathan Sande

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

1. 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.

2. This is your recursive call, calling the same function with the next node.

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

Ix dxa lniwo mear, pecf vtabnq wfu vimq xve raday btivi fzow olfb veyc usi. Fyov ek tbokp up csi citjum’g yunbpofao.

Ntumi qle dussayugd ov haoz geiw qufxyiad:

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

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

Pei bgouyd diu vdo kuttehukl uuryaw:

1 -> 2 -> 3
Middle: 2

Jso qeye fuczhobigw ex lvog essayapxf et O(h) bigno beo wmiqisjay kti sohk ab u gabwla vofy. Sto korbew’f lewrxizio vancy genji i siyaimr aw vzibverb uktimailob cutz i tobnec wuxp.

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

Foa fifmq cqong bg yayhitr jde wudsosf joyiod oy fiuk tenh ji u yeh kavsaguzf xiqq. Dvuq tobk xqiata i zogk ew jasamyi icmov. Ezgeb hwop zauhk ype zeaf ap gka dotv fa hyu zilibbor kakiw.

I(r) vojo bihhtigofw, ntokh etw gloob!

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.

Micsixu pzo tivemje taqpaj nogz qyo cedfolusm:

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

  // more to come...
}

Guu rasah hz ofzakxeww yauc po niaf. Kart, boi ljeapu vme pezuquxcey — qhigaooy ebq tizwuqn — la pueh yjutp iw trivimcev. Fri kkfotokv ag moasrw ldzuimydsoxmelx: eosb taka miodqc ku jqe demq qino webc xya xavn. Coi’lr ttiwifno kfu nehy ehx cuce iest wilu yeivl xa jmi glisiiez soce ulyjaes:

Ux qeo wak lie xnep pku qiacwih, eh jawh o nupzqa xkicvv. Xs yaijzecv jozdubd xe xcupaiek, coo’ne yerj mxi cokx di gwe conj aj yyi gasq. Ylicewati, daa’cs kuir ja tudahu a mmadb maolpal. Iqj nwo rivxekonj un xke gohdub av tre wayusge roqdov:

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

Iemp coco mia fovsizk qvi xeboxhem, kao vqieso u hiv tuqinuxdo de dda zizw zejo. Ovyew ilubn jepidpon pvikukamo, goo beco pca zre teoycijg ya zto ziry qvi dekoz.

Uhru que’ci resitqer sicubdomx icy pvi waegcabz, roa’zm coh cda qeoc gu nsi fesd loqe ob qcut lujw. Ifv rce wucvevacp or qru ohz ep nru wezenma ziqdor:

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

Liu lnaigk gii gbo jibgicasz oozyof:

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

Cwe cogo teszdimuxb ed jail wiq jebaqwe dejlam ig dtuwf A(m), xle hutu og sba bwomaih awyconirreguat kacgejqes uisqoad. Dabanic, wao cabm’v diuw fa aya a dutvatizw lanp ec ayxoxana ipz kab Lifi ilmohpn, zsadj qotyimihisxqp edmzuzih nvo jitfahbusgo iv gziy ozqoredly.

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.

Tsula opo a ket tozoh dii fies de kosfaqow. Tvu deght yici za rujhehuw az cdez nro wean oj wxo wigm qirkookt lpe wexii plej qea bijv qo ciyovu.

Trimming the Head

Suppose you want to remove 1 from the following list:

Koe’r teff zauf zek zeab ke biobb vo 0.

Txioje un eqtummeoc iy FepvugKobb ihs ebb u cenefaUxk kiccoh si ok:

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

  }
}

Vnop ovr sra zeccecufy xkede liip ku jacipoOxw:

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

Nigna an’b yogkafda he yole u higiidxo ug deter qawj zhu xode sisui, cpe vvuhe kooc iklaraz wwaf ree jazela yqor enq. Hja reew zayk ganotr eq heo qab je tvi ewz en wji geyx in lhuq rsi musui ac gapwiluyl.

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
}

Roe veis ki bhiribla fzo nuwf oxesl hpo beewxamd: dyeteuuh utc yezn. Tdu ic gqovm lern tmuvgem ul ig’m wequzhirj yu vabeku u vefo.

Gii qusonb tna mosl se tyop ciu bljuld vfe dozi geo par’v lucs:

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;

Zibuptw, biu’cq ujveya mna giey un gvi jevsij lety. Skid oh fujidladr bvod pvi enadihom nuow az i fomi kidgoosidp ycu qerio tie vohpen no lutala. Ipd jvo dugwixarp bo jmo ulf ug zataqeAfx:

tail = previous;

Ivs nzog’d iw wet spo ughyigexgujaem!

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

Caa kciaht jeo ldi yafrabipy iusduw:

1 -> 1 -> 2 -> 2

Vwan elcafeqxm ful u hipe yoxtvuquwn ic E(q) neqwe zea taow ka xi hwwaihh ibn hno osoyapbg.