Sweaty Imposter

Reverse Linked List

EasyIn-Place Reversal of LinkedListBlind 75JuniorOpen on LeetCodeUpdated

You're given the head of a singly linked list. Reverse it so the last node comes first and every link points the other way, then return the new head. Rearrange the existing nodes' next pointers rather than building a new list or copying values around. An empty list (a null head) is returned as an empty list.

Examples

head = [1,2,3,4,5] returns [5,4,3,2,1]

input
1head2345null
output
5head4321null

Every link flips direction: 5 now points to 4, 4 to 3, and so on, while 1 becomes the tail and points to null. The old tail 5 is the new head.

head = [] returns []

An empty list has no links to flip, so the result is also empty (a null head).

Constraints

  • 0 <= n <= 5000

Hints

Hint 1

What three node references would you need to keep around to flip arrows one at a time?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Walk the list once with three references: prev (the reversed part so far, starting at null), curr (the node being processed) and a saved next. For each node, save curr.next, point curr.next back at prev, then step prev to curr and curr to the saved next. When curr falls off the end, prev is the old tail, which is the new head. O(n) time, O(1) extra space.

Time

O(n)

Space

O(1)

Pitfall

Setting curr.next = prev before saving the original next, which cuts off the rest of the list. Also return prev, not curr: when the loop ends curr is null and prev is the new head.

Solutions

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