206. Reverse Linked List

easy linked-list

Reverse a singly linked list.

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

Approach

Iterative: use three pointers (prev, curr, next) — O(n) time, O(1) space.

Solutions

Ruby

class ListNode
  attr_accessor :val, :next
  def initialize(val = 0, next_node = nil)
    @val = val
    @next = next_node
  end
end

def reverse_list(head)
  prev = nil
  curr = head
  while curr
    next_node = curr.next
    curr.next = prev
    prev = curr
    curr = next_node
  end
  prev
end

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head: ListNode | None) -> ListNode | None:
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

Go

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    return prev
}

TypeScript

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val ?? 0;
        this.next = next ?? null;
    }
}

function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let curr = head;
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Elixir

defmodule Solution do
  def reverse_list(head) do
    do_reverse(head, nil)
  end

  defp do_reverse(nil, prev), do: prev
  defp do_reverse(%{val: val, next: next}, prev) do
    do_reverse(next, %{val: val, next: prev})
  end
end