Reversing a Linked List

I’m currently going through solving common data structure/algorithm questions that iOS developers have encountered and reversing a Linked List is one of them. The first thing we need to do is build the bare bones of a Linked List.

So what we’ve done is compiled the list of nodes, oneNode, twoNode and threeNode that will be our list. Let’s write a function to print out our Linked List just to double-check everything is in the correct order.

Look at the printout.

In order to truly understand how we should reverse the linked list, let’s user some arrows to indicate how each node is referencing each other and what it should look like in the end.

Currently our Linked List looks like this:

1 →2 →3 →nil

What we want is….

3 →2 →1 →nil

The manner in which we should go about reversing our list should look like the following:

nil ←1 →2 →3 →nil

nil←1←2 →3 →nil

nil←1←2←3

What we are trying to accomplish is quite different from reversing an array, which is a situation where you could simply begin iterating from the last element and end with the first one. This is a matter of actually reversing pointers and making sure that the head and tail along with all their next values are properly changed.

Let’s go through what is happening here. We set our currentNode to equal to the head, the first node in our Linked List. The currentNode is also the variable we will be using to define our conditional statement within the while loop. Next we have two more variables, the previousNode and the nextNode, which will also be subject to impending changes. We want to loop through our list as long as the currentNode is not equal to nil, we want to break out of the loop if it does become nil. The visualization of 1 →2 →3 →nil is helpful here.

So the first thing we do is set the nextNode to equal to the next node of our currentNode. So we begin in the list with 1 being the head node, and we just set the nextNode to become 2, hence nextNode = currentNode?.next. I then switched gears a bit to write the last line of code before the return statement, which was currentNode = nextNode because to me that made the most logical sense, when we are done altering references to all other variables we would want a new head node to iterate over and recalculate all our other values.

Now comes the tricky part…what do we do with the previousNode and the the currentNode’s next property? In our loop the values for our previousNode are the following thus far nil, 1, 2. If we are incrementing we would want the values to become 1, 2, 3 or previousNode to equal the CurrentNode. However, we still have to accommodate for currentNode?.next which points to previousNode before we alter it. Essentially we are flipping the values for currentNode?.next and previousNode, if we comment out this line then you’ll notice that the list of nodes does not print, it stops at 3. currentNode?.next = previousNode is helping keep track of what previous nodes came before the thirdNode.

Then when we think about the next iteration of out loop we set the previousNode to become the currentNode, since it is the next node in the list. Finally, you change the currentNode to be the nextNode to continue onto the next node value. You return the previous node because we want to return the new ‘head’ or initial node in our Linked List.