In a previous lesson, we looked at how you can code up your own link list data structure, a common follow-up interview question is to reverse the link list in place. This is a question so famous that at this point it is basically a meme. So in this lesson we will discuss a simple mental model and a solution to this problem. So let's jump right in. We start off by bringing in the link list and the link list node from a link list module. The key task at hand is to write this function called reverse link list that takes an input link list and reverses the order of the elements within the list in place. Here's the quick recap of the link list data structure.

We have a list of nodes where each node has a value of type T and it can be anything like a string order number that we store against the node, and then it has a member called next, which points to the next node within the chain. And the final element will actually point to now the first node is the head and the last node is the tail. Now our objective with the reverse link list function is to reverse the order of the next pointers. So for any node A that was pointing to node B, we should make it such that B will now point to A. So every next node should start

pointing to the previous node. And of course, for the first node, it'll start pointing to. Now let's start by coding up a simple version of what we want. Fundamentally, we will simply loop through the nodes and for each node we will update its next pointer to point to the previous node to store the previous node. We create this variable called previous, and we initialize it to now because when we start from list head, it'll have no previous node and therefore it'll be now. Next we write a basic loop to go through all of the nodes in the link list. We are clearly starting off at the head,

and if it is not now, then we update its next pointer to the previous node, and then we kick off the next iteration by setting the previous to current and current to current.next. Now that's the general extent of the algorithm that you actually need. However, there are two more things that you need to remember in order to do this correctly. First, note that when we replaced current next, we can actually no longer use it to go to the next value as it's now wanting to the previous member. Now, that's easily fixed by storing the reference in a temporary variable before we do the replacement

and then using this temporary variable to go to the next node. Now the other thing that you need to remember is that list head needs to point to the last node in the original list. In this particular data structure, we are storing the head as well as the tail. So it's an easy swap between the two variables. By the way, if this method of swapping JavaScript variables is new to you, I have a lesson dedicated to this that I will leave in the video description. Now the space complexity is OF one because we are reversing the original nodes in place and only need to allocate a constant amount

of additional space and time. Complexity is OFN because we need to loop through all of the nodes and therefore this will be done in linear time. And that is it. You've successfully reversed an input link list in place. Now let's do a quick demo To demonstrate that it actually functions. We create a link list and then add the values 1, 2, 3, 4 in that order, invoke reverse link list on this particular example and then iterate through the values of the link list. And we expect to see 4, 3, 2, 1, and that is exactly what we see in the output.

The in-place reversal of the link list is not a coding algorithm that is particularly complex. You just need to remember a few key things. Every next node should point to the previous node, and before you do this replacement, make sure you store the old next member so that you can use it to continue the iteration. And finally, the new head should point to the old tail and the new tail should point to the old head. And with that, you should be able to code it up on the fly.