Reverse Linked List

Learn how to solve this Data Structures and Algorithms problem so you can ace your next interview.

Linked Lists

Stacks

easy

Written by

Kenny Polyack

Software Engineer

Kenny is a software engineer and technical leader with four years of professional experience spanning Amazon, Wayfair, and U.S. Digital Response. He has taught courses on Data Structures and Algorithms at Galvanize, helping over 30 students land new software engineering roles across the industry, and has personally received offers from Google, Square, and TikTok.

Tom Wagner

Senior Software Engineer

Tom has four years of experience developing software professionally, including experience at both Amazon and Pinterest. He is experienced both as an interviewer, conducting interviews on behalf of the companies he's worked for, and interviewee, as he has landed software engineering offers from Google, Twitter, Stripe, Airtable and Doordash during previous job searches.

Interview Problems

About interviewing.io

interviewing.io is a mock interview practice platform. In our lifetime we’ve hosted close to 100K mock interviews, conducted primarily by senior engineers from FAANG.

We have the recordings from these mock interviews, as well as post-interview feedback and outcomes. We’ve curated information from these interviews and interviewers to bring you the best guidance on solving interview problems on the web!

Table of contents

  • Problem Description
  • Examples Inputs and Outputs
  • Example 1
  • Example 2
  • Example 3
  • Constraints
  • Problem Solution
  • Watch Someone Solve Reverse Linked List
  • Problem Approaches
  • Recursive Approach
  • Reverse Linked List Python and JavaScript Solutions - Recursive
  • Time / Space Complexity Analysis
  • Iterative Approach
  • Reverse Linked List Python and JavaScript Solutions - Iterative
  • Time / Space Complexity Analysis
  • Similar Questions

Problem Description

Given the head of a linked list, reverse the list and return the new head.

Examples Inputs and Outputs

Example 1

Input: [1,2,3,4,5]

Output: [5,4,3,2,1]

Example 2

Input: [1,2]

Output: [2,1]

Example 3

Input: [1]

Output: [1]

Constraints

  • The number of nodes in the list is in the range [0, 5000].
  • -5000 <= Node.value <= 5000

Problem Solution

Problem Approaches

To approach this problem, let's start with a concrete understanding of how a linked list works. Unlike an array, a linked list is a recursive data structure - each node points to another node - which means we don't have random access to its members. Instead, we're given a head node with a next property that points to the subsequent node in the list. Here's an example of a linked list with two nodes:

Reverse Linked List img 1-1

If this list were to be reversed, its clear that n2 would point to n1. But what would n1 point to? Recall that while n2 does not have a child, the node's next property still exists - it simply points to null. And while there is no node pointing to n1, we can imagine that its parent is null. So n1 would point to null.

Reverse Linked List img 1-2

We can imagine a null node at the head and the tail of the list.

At minimum, reversing a linked list will require updating each node's next pointer to reference its parent. Since we'll need to visit each node at least once, our solution space is limited to a linear traversal.

Let's explore how we can update each node in-place with a single traversal. A linked list can be traversed recursively or iteratively - in both approaches, we maintain a reference to the current node, its parent, and its child, and re-assign the next reference for each node.

Recursive Approach

Since a linked list is an inherently recursive data structure, it makes sense to consider a post-order recursive traversal to reverse the list. Why "post-order"? The key here is to recurse on each subsequent node until the last node is reached, and then update the next pointers as each execution pops off the call stack.

reverse_linked_list_2-1
reverse_linked_list_2-2

Each call to reverse_list is passed in a reference to the current node's child, which adds a new execution frame to the call stack.

reverse_linked_list_2-3
reverse_linked_list_2-5

Once a null node is reached (our base case), we begin the reassignment process. As each context is popped off the stack, we assign the current node's child's next pointer to the current node, effectively reversing its reference. Then return the reversed list so far.

reverse_linked_list_2-6

We also set the current node's next pointer to null - this will be overwritten once the subsequent recursive call is resolved, except for the original head which is now the tail and therefore has no next node.

REVERSE LINKED LIST PYTHON AND JAVASCRIPT SOLUTIONS - RECURSIVE
TIME / SPACE COMPLEXITY ANALYSIS

• Time Complexity: O(n)

• Space Complexity: O(n). Recursion requires linear space on the call stack to maintain a reference to each execution context.

Iterative Approach

Reversing a linked list iteratively is more space efficient than recursion, and tends to be more easy to grasp.

The task of any iterative traversal is managing pointers across iterations. First, let's set up our state-of-the-world for the head (input) node.

Reverse Linked List img 3-1

prev points to null (the head has no parent), curr points to the current node (the head), and, if there is indeed a current node, temp_next points to the current node's child.

Reverse Linked List img 3-2

At each itertion, we assign the current node's next pointer to the node at prev (reversing the reference). We then iterate forward by pointing prev to the current node and curr to the original next node.

Reverse Linked List img 3-3

We continue this process until a null child is reached - at which point we can return the most recent prev node which is our new head.

REVERSE LINKED LIST PYTHON AND JAVASCRIPT SOLUTIONS - ITERATIVE
TIME / SPACE COMPLEXITY ANALYSIS

• Time Complexity: O(n)

• Space Complexity: O(1)

Reveal solution

Similar Questions

Ready to practice with a mock interview?

Book mock interviews with engineers from Google, Facebook, Amazon, or other top companies. Get detailed feedback on exactly what you need to work on. Everything is fully anonymous.

Computer Dude