Revese a Linked List In-Place

Pro Members Only

This lesson is available if you have an active subscription.

Alternatively, some member might be able to gift it to you.

If you already have a subscription, you can sign in.

Revese a Linked List In-Place

Subscription Required

You must have an active subscription to access this content.
If you already have a subscription, you can sign in.

Problem

import { LinkedList, LinkedListNode } from '../linkedList/linkedList';

/**
* Reverse a linked list in place
*/
export function reverseLinkedList<T>(list: LinkedList<T>) {

}

Solution

import { LinkedList, LinkedListNode } from '../linkedList/linkedList';

/**
* Reverse a linked list in place
*/
export function reverseLinkedList<T>(list: LinkedList<T>) {
let previous: LinkedListNode<T> | null = null;
let current: LinkedListNode<T> | null = list.head;

while (current != null) {
// Copy before overwriting
let next = current.next;

// Reverse
current.next = previous;

// Step forward
previous = current;
current = next;
}

// Swap head and tail
[list.head, list.tail] = [list.tail, list.head];
}

Transcript

00:00 In a previous lesson, we looked at

00:01 how you can code up your own link list data structure,

00:04 a common follow-up interview question is

00:06 to reverse the link list in place.

00:08 This is a question so famous

00:09 that at this point it is basically a meme.

00:12 So in this lesson we will discuss a simple mental model

00:14 and a solution to this problem.

00:16 So let's jump right in. We start off

00:19 by bringing in the link list

00:20 and the link list node from a link list module.

00:23 The key task at hand is

00:25 to write this function called reverse link list

00:27 that takes an input link list

00:28 and reverses the order

00:29 of the elements within the list in place.

00:32 Here's the quick recap of the link list data structure.

00:34 We have a list of nodes where each node has a value

00:37 of type T and it can be anything like a string order number

00:40 that we store against the node,

00:42 and then it has a member called next, which points

00:45 to the next node within the chain.

00:46 And the final element will actually point to now

00:49 the first node is the head and the last node is the tail.

00:52 Now our objective with the reverse link list function is

00:55 to reverse the order of the next pointers.

00:58 So for any node A that was pointing to node B,

01:01 we should make it such that B will now point to A.

01:04 So every next node should start

01:06 pointing to the previous node.

01:08 And of course, for the first node, it'll start pointing to.

01:10 Now let's start

01:11 by coding up a simple version of what we want.

01:14 Fundamentally, we will simply loop through the nodes

01:17 and for each node we will update its next pointer to point

01:20 to the previous node to store the previous node.

01:23 We create this variable called previous,

01:25 and we initialize it to now

01:26 because when we start from list head,

01:28 it'll have no previous node and therefore it'll be now.

01:32 Next we write a basic loop to go through all

01:35 of the nodes in the link list.

01:37 We are clearly starting off at the head,

01:39 and if it is not now, then we update its next pointer

01:42 to the previous node,

01:43 and then we kick off the next iteration

01:45 by setting the previous to current

01:47 and current to current.next.

01:49 Now that's the general extent of the algorithm

01:51 that you actually need.

01:53 However, there are two more things that you need

01:55 to remember in order to do this correctly.

01:58 First, note that when we replaced current next,

02:01 we can actually no longer use it to go to the next value

02:04 as it's now wanting to the previous member.

02:06 Now, that's easily fixed

02:07 by storing the reference in a temporary variable

02:10 before we do the replacement

02:12 and then using this temporary variable

02:14 to go to the next node.

02:16 Now the other thing that you need to remember is

02:18 that list head needs to point

02:20 to the last node in the original list.

02:22 In this particular data structure,

02:24 we are storing the head as well as the tail.

02:26 So it's an easy swap between the two variables.

02:29 By the way, if this method

02:30 of swapping JavaScript variables is new to you,

02:33 I have a lesson dedicated to this

02:34 that I will leave in the video description.

02:37 Now the space complexity is OF one

02:39 because we are reversing the original nodes in place

02:42 and only need to allocate a constant amount

02:44 of additional space and time.

02:46 Complexity is OFN

02:48 because we need to loop through all of the nodes and

02:50 therefore this will be done in linear time.

02:53 And that is it. You've successfully reversed an input

02:55 link list in place.

02:57 Now let's do a quick demo

02:58 To demonstrate that it actually functions.

03:01 We create a link list

03:02 and then add the values 1, 2, 3, 4 in that order,

03:06 invoke reverse link list on this particular example

03:09 and then iterate through the values of the link list.

03:11 And we expect to see 4, 3, 2, 1,

03:14 and that is exactly what we see in the output.

03:18 The in-place reversal

03:19 of the link list is not a coding algorithm

03:21 that is particularly complex.

03:23 You just need to remember a few key things.

03:25 Every next node should point to the previous node, and

03:28 before you do this replacement,

03:30 make sure you store the old next member so

03:32 that you can use it to continue the iteration.

03:35 And finally, the new head should point to the old tail

03:38 and the new tail should point to the old head.

03:40 And with that, you should be able to code it up on the fly.