Reverse Linked List solution and explanation
Nokia
Infosys
Google
9 more videos on this problem
Reverse Linked List - Iterative AND Recursive - Leetcode 206 - PythonNeetCode · 11:07 · 700K views
LeetCode - Reverse Linked List SolutionNick White · 7:02 · 133K views
Reverse Linked List - Leetcode 206 - Linked Lists (Python)Greg Hogg · 8:02 · 39K views
LeetCode 206: Reverse Linked List | SWE InterviewAbstracted Away · 4:27 · 17K views
LeetCode 206: Reverse Linked List RECURSIVELY - Interview Prep Ep 60Fisher Coder · 12:01 · 15K views
LEETCODE 206 (JAVASCRIPT) | REVERSE LINKED LISTAndy Gala · 9:19 · 8K views
Reverse Linked List - LeetCode 206 - Python (Iterative and Recursive)Deepti Talesra · 15:53 · 5K views
Leetcode | 206. Reverse Linked List | Easy | Java SolutionDeveloper Docs · 6:37 · 4K views
Reverse Linked List | Leetcode - 206Algorithms Made Easy · 12:06 · 4K views
LeetCode 206: Reverse Linked List ITERATIVELY - Interview Prep Ep 59Fisher Coder · 11:55 · 3K views
The problem
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2] Output: [2,1]
Example 3:
Input: head = [] Output: []
Constraints:
- The number of nodes in the list is the range
[0, 5000]. -5000 <= Node.val <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
Approach overview
Problem Overview: Given the head of a singly linked list, reverse the list so that the last node becomes the first and every next pointer points to the previous node. Return the new head after reversal. The challenge is pointer manipulation without losing access to the remaining nodes.
Approach 1: Iterative Pointer Reversal (O(n) time, O(1) space)
This approach walks through the list once and reverses the next pointer of every node. Maintain three pointers: prev, curr, and next. For each node, store curr.next in next, redirect curr.next to prev, then advance both pointers forward. The key insight is preserving the next node before modifying the pointer so you never lose the remaining list. After the loop finishes, prev points to the new head of the reversed list. This is the most common solution because it runs in linear time and uses constant extra memory. Problems involving pointer manipulation like this appear frequently in Linked List interview questions.
Approach 2: Recursive Reversal (O(n) time, O(n) space)
The recursive approach reverses the list starting from the second node and fixes the first node during the backtracking phase. Call the recursive function on head.next until the base case (last node) is reached. When the stack unwinds, set head.next.next = head to reverse the pointer direction and then set head.next = null to terminate the list. The recursive call returns the new head, which propagates back through each stack frame. This approach is elegant and highlights how recursion can naturally handle pointer re-linking, but it uses additional call stack space proportional to the list length. It’s a common demonstration of recursion in Recursion and pointer-based structures.
Recommended for interviews: The iterative approach is typically expected because it achieves O(n) time with O(1) extra space and demonstrates strong pointer manipulation skills. Interviewers often accept the recursive version as well, but they may follow up by asking you to reduce space usage. Showing both approaches signals a deeper understanding of how linked list structures work and how pointer direction can be reversed safely.
Approach 1: Iterative Approach
Iterative Approach: This approach involves using a loop to traverse the linked list and reverse the direction of the next pointers at each step. Start with three pointers: prev as null, curr as the head of the list, and nxt to temporarily store the next node. In each iteration, change the curr.next to prev, move prev to curr, and curr to nxt. The loop ends when curr becomes null, with prev being the new head.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prevclass ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nxt = curr.next;
curr.next = prev;
prev = curr;
curr = nxt;
}
return prev;
}
}#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
while (curr) {
ListNode* nxt = curr->next;
curr->next = prev;
prev = curr;
curr = nxt;
}
return prev;
}function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
function reverseList(head) {
let prev = null;
let curr = head;
while (curr !== null) {
let nxt = curr.next;
curr.next = prev;
prev = curr;
curr = nxt;
}
return prev;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode* next;
};
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* curr = head;
struct ListNode* nxt = NULL;
while (curr != NULL) {
nxt = curr->next;
curr->next = prev;
prev = curr;
curr = nxt;
}
return prev;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nxt = curr.next;
curr.next = prev;
prev = curr;
curr = nxt;
}
return prev;
}
}In the Python implementation, prev, curr, and nxt pointers again maintain the structure necessary for iterative reversal. After resetting pointers, the head is reassigned to prev, which is the new head of the reversed list.
Time Complexity: O(n), because every node is processed.
Space Complexity: O(1), using a constant amount of space.
Approach 2: Recursive Approach
Recursive Approach: In this method, you move to the end of the list via recursive calls while reversing the next pointers on the way back. The base case for the recursion is when the list is empty or when it contains only one node. In each call, move to the next node, reverse the rest of the list, use the next pointer's next field to point to the current node, and finally return the head of the reversed list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return pclass ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
}#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* p = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return p;
}function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
function reverseList(head) {
if (head === null || head.next === null) return head;
let p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode* next;
};
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL || head->next == NULL) return head;
struct ListNode* p = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return p;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode ReverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = ReverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
}The Python recursive solution involves recursively calling the reverse function until reaching the end of the list, then reversing the next pointers on the return path of the recursion.
Time Complexity: O(n), iterating over n nodes.
Space Complexity: O(n), for the recursion call stack.
Approach 3: Head Insertion Method
We create a dummy node dummy, then traverse the linked list and insert each node after the dummy node. After traversal, return dummy.next.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function reverseList(head: ListNode | null): ListNode | null {
if (head == null) {
return head;
}
let pre = null;
let cur = head;
while (cur != null) {
const next = cur.next;
cur.next = pre;
[pre, cur] = [cur, next];
}
return pre;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
dummy := &ListNode{}
curr := head
for curr != nil {
next := curr.Next
curr.Next = dummy.Next
dummy.Next = curr
curr = next
}
return dummy.Next
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut head = head;
let mut pre = None;
while let Some(mut node) = head {
head = node.next.take();
node.next = pre.take();
pre = Some(node);
}
pre
}
}Approach 4: Recursion
We recursively reverse all nodes from the second node to the end of the list, then attach the head to the end of the reversed list.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the linked list.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
const rev = (pre: ListNode | null, cur: ListNode | null): ListNode | null => {
if (cur == null) {
return pre;
}
const next = cur.next;
cur.next = pre;
return rev(cur, next);
};
function reverseList(head: ListNode | null): ListNode | null {
if (head == null) {
return head;
}
const next = head.next;
head.next = null;
return rev(head, next);
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
ans := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return ans
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
fn rev(pre: Option<Box<ListNode>>, cur: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match cur {
None => pre,
Some(mut node) => {
let next = node.next;
node.next = pre;
Self::rev(Some(node), next)
}
}
}
pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
Self::rev(None, head)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n), because every node is processed. |
| Recursive Approach | Time Complexity: O(n), iterating over n nodes. |
| Head Insertion Method | – |
| Recursion | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Pointer Reversal | O(n) | O(1) | Preferred solution in interviews and production when constant memory is required |
| Recursive Reversal | O(n) | O(n) | Useful for demonstrating recursion concepts or when recursive style is preferred |
Frequently asked questions
Is Reverse Linked List easy or hard?
Reverse Linked List is classified as an Easy problem on LeetCode. The core idea is straightforward once you understand pointer updates, but beginners often struggle with losing references to the remaining nodes during reversal.
Reverse Linked List Python/Java solution
Both Python and Java implementations follow the same pointer manipulation logic. Maintain three references (prev, curr, next), iterate through the list, and reverse the next pointer at each step. The algorithm remains O(n) time and O(1) space across languages.
How to solve Reverse Linked List in O(n)?
Traverse the list once while updating pointer directions. Store the next node temporarily, set the current node's next pointer to the previous node, then move both pointers forward. After processing all nodes, the previous pointer becomes the new head of the reversed list, achieving O(n) time and O(1) space.
What is the best approach for Reverse Linked List?
The iterative pointer reversal approach is the best solution for most cases. It traverses the list once and reverses each node's next pointer using three variables (prev, curr, next). The algorithm runs in O(n) time and uses O(1) extra space, which is optimal for this problem.
Is Reverse Linked List asked at Google/Amazon/Meta?
Reverse Linked List is one of the most common linked list interview questions and has appeared in interviews at companies like Amazon, Google, Meta, and Microsoft. It tests pointer manipulation, understanding of linked list structure, and ability to manage references safely.
What data structure is used in Reverse Linked List?
The problem uses a singly linked list where each node stores a value and a pointer to the next node. The algorithm works by reassigning these next pointers so that each node points to its previous node instead of the next one.
What is the time complexity of Reverse Linked List?
Reversing a linked list requires visiting each node exactly once, giving a time complexity of O(n), where n is the number of nodes. The optimal iterative solution uses O(1) additional space, while the recursive approach uses O(n) space due to the call stack.