Scale Engineer

Reverse Linked List

Easy
#0194Time: O(n) where n is the number of nodes in the linked list - we need to traverse each node onceSpace: O(n) due to the recursive call stack - we make n recursive calls for n nodes30 companies
Patterns
Recursion
Data structures
Linked List
Companies
AccentureByteDanceCiscoDeloitte

Prompt

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

  1. Base case: if head is null or head.next is null, return head
  2. Recursively call reverseList on head.next until reaching the end
  3. For each recursive call during backtracking:
    • Set head.next.next = head (reverse the link)
    • Set head.next = null
  4. Return the new head of reversed list

Walkthrough

The recursive approach works by:

  1. First, we need to reach the end of the linked list through recursion
  2. As we backtrack, we reverse the links between nodes
  3. 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]:

  1. First recursive call: head = 1, calls reverseList(2)
  2. Second recursive call: head = 2, calls reverseList(3)
  3. Third recursive call: head = 3, returns 3 as it's the last node
  4. Backtrack to 2: makes 3->2, 2->null
  5. Backtrack to 1: makes 2->1, 1->null
  6. 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

Solutions

/** * 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 ; } }

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.

← Previous

Previous problem

Next →

Next problem