Reverse Linked List
EasyPrompt
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?
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses recursion to reverse the linked list by recursively reaching the end of the list and then backtracking to reverse the links.
Algorithm
- Base case: if head is null or head.next is null, return head
- Recursively call reverseList on head.next until reaching the end
- For each recursive call during backtracking:
- Set head.next.next = head (reverse the link)
- Set head.next = null
- Return the new head of reversed list
Walkthrough
The recursive approach works by:
- First, we need to reach the end of the linked list through recursion
- As we backtrack, we reverse the links between nodes
- Finally, we set the head's next to null to complete the reversal
Here's the implementation:
public ListNode reverseList(ListNode head) { // Base cases: if head is null or we've reached the last node if (head == null || head.next == null) { return head; } // Recursively reach the last node ListNode reversedList = reverseList(head.next); // Reverse the link between current node and next node head.next.next = head; head.next = null; return reversedList;}Let's see how it works with example [1,2,3]:
- First recursive call: head = 1, calls reverseList(2)
- Second recursive call: head = 2, calls reverseList(3)
- Third recursive call: head = 3, returns 3 as it's the last node
- Backtrack to 2: makes 3->2, 2->null
- Backtrack to 1: makes 2->1, 1->null
- Final result: 3->2->1->null
Complexity
Time
O(n) where n is the number of nodes in the linked list - we need to traverse each node once
Space
O(n) due to the recursive call stack - we make n recursive calls for n nodes
Trade-offs
Pros
Clean and elegant solution
Easy to understand the logic
Good for learning recursive thinking
Cons
Uses extra space due to recursive call stack
Can cause stack overflow for very large lists
Not as space efficient as iterative approach
This approach uses three pointers to iteratively traverse the list and reverse the links between nodes. It's more space-efficient than the recursive approach.
Algorithm
- Initialize three pointers: prev=null, curr=head
- While curr is not null:
- Store next = curr.next
- Reverse link: curr.next = prev
- Move prev = curr
- Move curr = next
- Return prev as new head
Walkthrough
The iterative approach maintains three pointers:
- prev: points to the previous node (starts as null)
- curr: points to the current node (starts as head)
- next: points to the next node (used to maintain the next reference)
Here's the implementation:
public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { // Store next node ListNode next = curr.next; // Reverse the link curr.next = prev; // Move prev and curr one step forward prev = curr; curr = next; } return prev;}Let's see how it works with example [1,2,3]:
- Initial state: prev=null, curr=1, next=2
- First iteration: 1->null, prev=1, curr=2
- Second iteration: 2->1->null, prev=2, curr=3
- Third iteration: 3->2->1->null, prev=3, curr=null
- Return prev as new head
Complexity
Time
O(n) where n is the number of nodes in the linked list - we need to traverse each node once
Space
O(1) as we only use three pointers regardless of input size
Trade-offs
Pros
Constant space complexity
No risk of stack overflow
Generally faster than recursive approach
More memory efficient
Cons
Slightly more complex to understand at first
Requires keeping track of three pointers
Code might look less elegant than recursive solution
Solutions
Solution
/** * Definition for singly-linked list. * 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 pre = null ; for ( ListNode p = head ; p != null ;) { ListNode t = p . next ; p . next = pre ; pre = p ; p = t ; } return pre ; } }public class Reverse_Linked_List { /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ /* 1,2,3,4,5 2,1 prev=2 - 3,4,5 current=3 3,2,1 prev=3 - 4,5 current=4 ... */ // https://leetcode.com/problems/reverse-linked-list/solution/ class Solution_oj_iterative { public ListNode reverseList ( ListNode head ) { ListNode prev = null ; ListNode curr = head ; while ( curr != null ) { ListNode nextTemp = curr . next ; curr . next = prev ; prev = curr ; curr = nextTemp ; } return prev ; } } class Solution_oj_recursively { 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 ; } } class Solution_recursively { public ListNode reverseList ( ListNode head ) { ListNode dummy = new ListNode ( 0 ); // dummy.next = head; ListNode current = head ; reverse ( dummy , current ); return dummy . next ; } private void reverse ( ListNode dummy , ListNode current ) { if ( current == null ) { return ; } ListNode newHead = current . next ; ListNode oldDummyNext = dummy . next ; dummy . next = current ; current . next = oldDummyNext ; current = newHead ; this . reverse ( dummy , current ); } } class Solution_iteratively { public ListNode reverseList ( ListNode head ) { ListNode dummy = new ListNode ( 0 ); // dummy.next = head; ListNode current = head ; while ( current != null ) { ListNode newHead = current . next ; ListNode oldDummyNext = dummy . next ; dummy . next = current ; current . next = oldDummyNext ; // initial node, oldDummyNext is null, which is what we want, and which is why "// dummy.next = head;" is commented out above current = newHead ; } return dummy . next ; } } } ############ /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList ( ListNode head ) { ListNode dummy = new ListNode (); ListNode curr = head ; while ( curr != null ) { ListNode next = curr . next ; curr . next = dummy . next ; dummy . next = curr ; curr = next ; } return dummy . next ; } }/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function (head) { let dummy = new ListNode(); let curr = head; while (curr) { let next = curr.next; curr.next = dummy.next; dummy.next = curr; curr = next; } return dummy.next; };# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def reverseList ( self , head : Optional [ ListNode ]) -> Optional [ ListNode ]: pre , p = None , head while p : q = p . next p . next = pre pre = p p = q return pre class Solution ( object ): # recursive def reverseList ( self , root ): if not root or not root . next : return root ret = self . reverseList ( root . next ) root . next . next = root # root.next is end of the newly reversed list ret root . next = None return ret class Solution : def reverseList ( self , head : ListNode ) -> ListNode : dummy = ListNode () curr = head while curr : next = curr . next curr . next = dummy . next dummy . next = curr curr = next return dummy . next// OJ: https://leetcode.com/problems/reverse-linked-list/ // Time: O(N) // Space: O(1) class Solution { public: ListNode * reverseList ( ListNode * head ) { ListNode h ; while ( head ) { auto p = head ; head = head -> next ; p -> next = h . next ; h . next = p ; } return h . next ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.