Reversing a Linked List, but as a Children’s Story
Once upon a time, there was a magic bridge…
The magic bridge was made up of round, magic stepping stones, and each magic stepping stone had a magic rope connected to it that pointed in one direction. The magic bridge had two rules that you always had to follow if you wanted to travel across it:
- You can only walk along the magic rope in the direction that it is pointing
- The magic bridge will continue on forever until one of the magic ropes points to an “end” sign.
One day, two engineers were standing at the entrance to the magic bridge.
The red engineer said to the blue engineer, “It’s sad that this bridge only goes in one direction. We’re always going from here to there, but what if the engineers over there want to come here?”
The engineers started thinking of ideas on how to reverse the direction of the bridge. Suddenly, the blue engineer realized a loophole in the bridge’s rules.
“I know we can only walk along the tightrope in one direction,” said the blue engineer, “but what if we could jump from stone to stone without having to step foot on the tightrope at all?”
“Brilliant!” exclaimed the red engineer. “But these stones are not very large and we could easily fall off the bridge if we’re not careful jumping. One of us should always be one stone ahead to catch the other when they try to jump.”
Excited to exploit the loophole and reverse the bridge, the blue engineer stood on the first stone while the red engineer stood at the entrance to the bridge.
“Hold on,” said the red engineer. “Remember the second rule of the bridge: It will continue on forever until the final stone points to an end sign. We need to put an end sign right here, because where I’m standing will eventually be the end.”
“Good thinking,” said the blue engineer. “Now I can take the rope on the first stone and have it point back to the end sign. Then you can jump over the rope and join me on the first stone!”
The blue engineer took the rope and pointed it towards the red engineer.
Since the blue engineer was already at the first stone, the red engineer was able to jump over the first stone knowing that the blue engineer would be there to catch him.
“Well dang,” said the engineers — having realized their predicament.
Their strategy had worked well for first stone, but now they couldn’t get to the second stone. They couldn’t walk to the next stone because there was no magic rope, and they couldn’t jump to the second stone because there was nobody there to catch them.
This was going to be harder than they thought. “We need a third engineer,” said the red engineer.
The engineers reset the bridge to its original state and sought out a third engineer to help them with their problem.
“I have an idea,” said the green engineer. “What if I go to the second stone before the blue engineer changes the direction of the magic rope on the first stone? That way when the blue engineer is done, he can jump over and join me on the next stone over!”
Following the magic rope, the green engineer walked to the second stone, the blue engineer walked to the first stone, and the red engineer stood at the end sign.
First the blue engineer grabbed the rope at the first stone and pointed it back to the red engineer.
“Careful now,” said the green engineer. “If the blue engineer joins me at the second stone right now, the red engineer won’t have anyone to catch him when he jumps to the first stone.”
Heeding the green engineer’s advice, the red engineer jumped over the magic rope to the first stone where the blue engineer was already standing to catch him.
“Perfect,” said the green engineer. “Now the blue engineer can jump over here and join me! I’ll be here to catch him, so it’s not a problem that there isn’t a rope between us.”
Starting to see the pattern, the blue engineer jumped to the second stone with the green engineer.
Knowing he needed to lead the way, the green engineer then walked across the magic rope to the third stone.
The pattern was now totally clear. The blue engineer pointed the rope at the second stone back towards the red engineer…
…then the red engineer jumped over to join the blue engineer…
…then the blue engineer jumped over to join the green engineer…
…and finally, the green engineer walked across the rope to the fourth stone.
Finding themselves in a groove, the engineers continued to follow their pattern.
Once the blue engineer finally got to the end sign, the team knew they had fully reversed the magic bridge and they lived happily ever after.
So how does it look in code?
Reversing a linked list depends heavily on its order of operations. Using the characters and props above, let’s represent this story with some pseudocode.
Brilliant! Everything here almost works perfectly well, we just have to do two things:
- Replace the “end signs” with null values
- Replace the .nextStoneOver and .magicRope properties with .next values
Once we’ve done that, the code above will look like this:
This code works perfectly well to reverse a linked list, but your prospective employer will probably have less of an adverse reaction if you name your variables something more descriptive than colors and change firstStone to head.
