EasyBlind75Linked List

Reverse Linked List

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

Examples

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

The linked list is reversed.

Input
head = [1,2]
Output
[2,1]

The linked list is reversed.

Constraints

  • •The number of nodes in the list is [0, 5000]
  • •-5000 <= Node.val <= 5000

Approaches

Traverse the list, store values in an array, and create a new reversed list.

CodeT: O(n) | S: O(n)
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    values = []
    curr = head
    while curr:
        values.append(curr.val)
        curr = curr.next
    dummy = ListNode(0)
    curr = dummy
    for val in reversed(values):
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next

Use three pointers to reverse the links between nodes.

CodeT: O(n) | S: O(1)
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

Recursively reverse the rest of the list, then fix the current node's pointer.

Diagram

1->2->3->4->5->None Reverse 2->3->4->5: new_head=5 Fix: 2.next=1, 1.next=None Result: 5->4->3->2->1->None
CodeT: O(n) | S: O(n)
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    if not head or not head.next:
        return head
    new_head = reverse_list(head.next)
    head.next.next = head
    head.next = None
    return new_head

Complexity Comparison

Iterative with Extra Space
T: O(n)S: O(n)

Traverse the list, store values in an array, and create a new reversed list.

Iterative - Three Pointers
T: O(n)S: O(1)

Use three pointers to reverse the links between nodes.

Recursive
T: O(n)S: O(n)

Recursively reverse the rest of the list, then fix the current node's pointer.

Common Mistakes

Losing reference to the next node before updating the current node's pointer

Not returning the correct new head of the reversed list

Creating a cycle by not setting the last node's next to None

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems