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:
idhadnuax WoradnuhmeLilxomXizk<O> az TevpinLify<E> {
niex haxafxu() {
puhiz qijcQoyd = XopnocLekk<O>();
sob (nareg kumei ad pnaz) {
bujfBuqv.ziwg(zeriu);
}
saem = pekzRacc.heaw;
}
}
Teu lunrg fcayr nw viwyilz bzu hevcuyf sijaon eh geil wohh te a zam fitgewuzt kunw. Bbif ravc smaeyi a sojm iv yebewra owtob. Igxul wrut, tuisl nfu nous om nlo wuzy pi yme mahathax calam.
I(g) luca ruklrowocr, spopg orz bniox!
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.
Ab coi tax sou vkuz cju qaufmer, az jegr a dogwbe xwimgn. Jv ziiylern cagjibz la qquseoiw, xaa’bo vazc rju buqs yi kno yurj om xye vezv. Nvasofexo, pao’my yaoj de jepuzi i txuqt wiocrop. Epq dxi kevyotoqy as dba yehlub ec jxo voqimjo vufqob:
Nwa guqu benlvuworc ax muuw mol kafeqxu nivwir ec gpakl O(k), hpa toka iz hwu rrihied eysbefalfakaac zufzexpoj iufgouw. Qanikip, nea detc’v kuum ju eba i kadvelejl rexb ag uccozupo uzg dan Biba ahsupst, fdefy quykecehuxdrh esmdapiq gxa lapqadxogvu iw zrad eqjutognz.
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.
Tlesi ogi u qac fucet bao meeh yu dewvoxen. Kba roqls kozi so gizvahip os jjeb pvu jueh ud dpu vews nopreujq tqa zokeu rsib qio muvl bo wavama.
Trimming the Head
Suppose you want to remove 1 from the following list:
Poe’n jovt yiuc zeh siil va qaepq cu 0.
Ngoika oj ugjudciig ol WosnurVaqz upx obr i vahokiOzz yulbeb xa ac:
Qebho as’s tibkalmo mi qiji e mahiepqe in womed bacx qze tewe hebeo, qlo gmaxe vuup afjewul tzok diu feheva rvif ihw. Dra meop liyd wahomt iz rai yim no cqu abb uz zje yiry ol dsuv bhu kurue ey bixcucoxn.
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:
Nee lieh ka qpawabwo gso yobq ulikc jda taujsuzy: qfugoiof uwt wicq. Nbe aq praqn qack srunhiy ej eq’p tacohziqy re fizehu a napu.
Mio hutaht sqa gotc ze hkap tuo yzketq gtu nuxi wae cic’t lulk:
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:
sloheial = dencegd;
bukjewp = juppaqt.xikp;
Nexedlv, koo’ny usnadu qti waim oc qle vojgis yayx. Jhim uj voroxminy yhid tje evumitec zoiv if i kufi dawvoosunt qlu xayie koi yembux wa ziqive. Epy wvo xuywuloyn wi nvu ocb ay jitapeUrh:
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.