Reverse Linked List

Easy Problem 48 of 151 Java and Python

Practice on LeetCode

Problem

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

Example 1

Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

Example 2

Input: head = []
Output: []

Constraints

0 ≤ number of nodes ≤ 5000
-5000 ≤ Node.val ≤ 5000

Explanation

Reversing means every arrow points the other way. Walk the list and turn each node's next to point at the node before it.

Before changing curr.next, save it, or you lose the rest of the list. That is why you need three pointers: prev, curr and next.

Approach 1 · Naive

Copy values, write them back reversed

Time O(n)
Space O(n)

Read the values into an array, then walk the list again writing them back from the end of the array.

Collect every value in a list.
Walk the nodes again, assigning values from the end of the list backwards.

Java

import java.util.*;

class Solution {
    public ListNode reverseList(ListNode head) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) {
            values.add(node.val);
        }
        int i = values.size() - 1;
        for (ListNode node = head; node != null; node = node.next) {
            node.val = values.get(i--);
        }
        return head;
    }
}

Python

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        values = []
        node = head
        while node:
            values.append(node.val)
            node = node.next
        node = head
        while node:
            node.val = values.pop()
            node = node.next
        return head

Approach 2 · Optimal

Iterative pointer reversal

Time O(n)
Space O(1)

Flip one arrow at a time while walking forward.

Set prev = null, curr = head.
While curr: save next = curr.next, set curr.next = prev, then move prev = curr, curr = next.
Return prev, the old tail.

Java

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

Python

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, curr = None, head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev, curr = curr, nxt
        return prev

Complexity compared

Approach	Time	Space
Naive Copy values, write them back reversed	O(n)	O(n)
Optimal Iterative pointer reversal	O(n)	O(1)

Key takeaways

Interviewers often ask for the recursive version too: reverse the rest, then head.next.next = head; head.next = null. It uses O(n) stack space.
Reversing a list is a building block for Palindrome Linked List, Reorder List and Reverse Nodes in k-Group.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem