Classic Linked List Problems: Reversing a Linked List and Removing an Element from a Linked List

Today we will be working with a linked list, a very common data structure. For an in depth analysis and implementation of a linked list class in JavaScript, please see my article here.

Linked List:

The beauty of a linked list is in its simplicity. It is a linear data structure that consists of nodes, each node contains a value and a reference to the next node on the list. By linear, we mean that we can only traverse the list in one direction, via the next pointer on each node.

Our Problems:

We will be examining two of the most classic problems related to linked lists, reversing a linked list as well as removing an element in a linked list.

Reverse a Linked List

From my experience, linked list problems are generally a measure of how well you manage your pointers. Our approach to this problem will be to change the current node’s next pointer to the previous node. In order to do this, we will need to make use of 2 pointers, the previous node, and the current node as well as a temporary node to use as a placeholder while we perform the swaps.

If you feel comfortable with linked lists then give it a try and compare it to my approach below:

Your reverse method should look something like the above

If you want to tinker with the code yourself you can check out the repo here. So like previously mentioned, this approach requires you to manage your pointers. The time complexity of reversing a linked list is O(n) as we need to traverse the entire list and has a space complexity of O(1) as we’re creating a set amount of variables when we run this algorithm.

Removing an Element From a Linked List

In this problem, the head of a linked list and a target value will be given. The goal will be to remove all nodes with that value.

Again, similar to our above approach we will be making use of 2 pointers. A pointer to the current node and one to the previous node. In addition to the pointers, we will be making use of a dummy/sentinel node. Deleting a ‘middle node’ is fairly straightforward, we traverse to the following node and set the previous node's next pointer to the furthest node.

Deleting Node, courtesy of geeksforgeeks

Using a dummy node covers cases where the head of a linked list needs to be deleted. We essentially convert our process to only the deletion of middle nodes.

Your remove method should look like the above

Again the above repo can be found here if you want to tinker with this code. The above is a one-pass solution so its time complexity is O(n) and space complexity of O(1). Feel free to leave optimized approaches or different solutions in the comments! Thanks for taking the time to review my approaches.