How to reverse a linked list in less than 5 minutes

The “reversing a linked list” problem has become quite popular, thanks to interviewers at various tech companies. It is a rather simple problem, but you’ll be surprised how many people get confused when trying to implement a solution for the same. Today, we will discuss the problem and implement a solution in Python, all in less than five minutes !

The Problem

Simply put, a linked list is nothing more than a collection of “nodes” or memory locations connected via pointers. The main difference between a linked list and array is that an array consumes a chunk of consecutive memory location while the nodes of a linked list can exist across non-consecutive memory locations and simply connected by a pointer to their location addresses. We can represent a linked list as follows

An empty linked list

Consider a linked list 1->2->3, where 1 is the head of the linked list. When asked to reverse a linked list, we simply change the re-assign the pointer the location of the previous node instead of the next node. When we do this for all the nodes, it will look something like this 1<-2<-3, where 3 is the new head of the list. The logic for this would be as follows:

  1. Store the location/address of the next node in a variable (you don’t want to lose this address !)
  2. Set the next property of the node to point to the previous node.
  3. Set the previous node variable to point to current node.
  4. Set the current node variable to point to the next node.
  5. Repeat steps 1,2,3&4 until you’ve reached the end of the linked list.

Let’s take a look at the implementation in Python.

Reversing the linked list

That’s it ! Hope this was helpful. Best of luck for that coding interview and stay tuned for more blogs like this one.

References

  1. https://www.geeksforgeeks.org/python-program-for-reverse-a-linked-list/

--

--

--

Grad Student (MTech in AI). Engineer. Musician. Yoga Instructor. Philomath. I write about anything that makes me curious. https://vijpandaturtle.github.io/

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Connect to Neo4j with PHP

A visual graph representation

Ever since I was a little boy, I have only ever wanted to be a Doctor.

Starting my journey to become a front-end developer

loc and iloc function in python

Udacity — GwG — Baking App (Day 6)

How Selenium and BeautifulSoup are Used for Scraping UberEATS Data?

AWS Lambda Basics — Writing Serverless Code

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
Vijayasri Iyer

Vijayasri Iyer

Grad Student (MTech in AI). Engineer. Musician. Yoga Instructor. Philomath. I write about anything that makes me curious. https://vijpandaturtle.github.io/

More from Medium

Algorithm in C++

How many merges (adjacent elements) it require for an array to be palindrome — Quicksort way

Adjecent Merges that might require an array to be a palindrome