206. Reverse Linked List

Today, we’ll be looking at the following problem:

206. Reverse Linked List

Prompt

Given the head of a singly linked list, we want to return that same linked list but in reversed order.

Approach

The main challenge here how do we reverse a singly linked list? As opposed to a doubly linked list that has an additional pointer commonly called prev which allows you to access the previous node, a singly linked list only has a single pointer that points to the memory address or reference of another node (commonly called next).

You could keep track of the previous node by instantiating a property called prev with the value of null at the beginning and while you traverse through the Linked List, continually set the prev to be the previous node.

prev = None

By doing this, this allows you to now set the .next connections of all the nodes in the linked list to be their respective prev or previous node. The key here though is to make sure to store the current iterated node’s next prior to manipulating the current iterated node’s next connection in order to not lose access to the next node from the original order of the Linked List.

cur = head
while cur != None:
temp = cur.next

Finally, update the prev variable to be the current iterated node and the current iterated note to the variable where you stored the current iterated node’s next.

prev = cur
cur = temp

Once the entire Linked List traversal is done, the Linked List should be reversed. You need to make sure you return prev because the while loop will terminate the current iterated node will be set to null. In other words, the current iterated node’s prev will be pointing to the head of the reversed Linked List.

return prev

Code

Python

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com