Coding problem · Easy · Linked List

Reverse Linked List

Easy Algorithms & data structures Most askedSeen at Amazon, Microsoft, Apple, Meta

Given the head of a singly linked list, reverse the list and return the new head. (Lists are shown as arrays in examples and tests.)

Example 1

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

Example 2

Input: head = []
Output: []

Hints

Hint 1

Walk the list keeping prev and current; point current.next back at prev.

Hint 2

Save current.next before you overwrite it.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1)

Iteratively flip each next pointer: next = cur.next; cur.next = prev; prev = cur; cur = next. When cur is null, prev is the new head. The recursive version is elegant but uses O(n) stack.

Reference solution

function reverseList(head) {
  let prev = null;
  let cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

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

def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]:
    prev, cur = None, head
    while cur:
        cur.next, prev, cur = prev, cur, cur.next
    return prev

<?php

function reverseList(?ListNode $head): ?ListNode
{
    $prev = null;
    $cur = $head;
    while ($cur !== null) {
        $next = $cur->next;
        $cur->next = $prev;
        $prev = $cur;
        $cur = $next;
    }
    return $prev;
}

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

Follow-up questions

Reverse only positions left..right (Reverse Linked List II).
Reverse in groups of k.

Merge Two Sorted Lists · Easy
Linked List Cycle · Easy
Remove Nth Node From End of List · Medium