Reverse Linked List

NeetCode: Reverse Linked List · LeetCode: 206. Reverse Linked List · Difficulty: Easy

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

Example

Text

Input:  1 -> 2 -> 3 -> 4    Output: 4 -> 3 -> 2 -> 1
Input:  (empty)             Output: (empty)

A ListNode holds an int val and a next reference. next is null at the end of the list, and an empty list is a null head. Linked structures in Java use null and mutable fields directly, so no wrapper type is needed. The fromArray helper builds a list from its values and toList reads one back, so the examples can print results.

Brute force: copy the values out, rebuild in reverse

Java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        List<Integer> values = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            values.add(cur.val);
        }
        ListNode newHead = null;
        for (int val : values) {
            newHead = new ListNode(val, newHead); // push onto the front
        }
        return newHead;
    }
}

public class Main {
    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(toList(s.reverseList(fromArray(1, 2, 3, 4))));
        System.out.println(toList(s.reverseList(fromArray())));
    }
}

Output

[4, 3, 2, 1]
[]

Pushing each value onto the front of a new list reverses the order. Time: O(n). Space: O(n) for the extra list and the new nodes.

Optimal: reverse the references in place

Walk the list with cur, keeping prev as the already-reversed part (null at first). At each node, save cur.next in a local variable, point the node at prev, and advance both. No node is allocated because every existing node is relinked, not copied.

Java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next; // save the rest before overwriting the link
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

public class Main {
    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(toList(s.reverseList(fromArray(1, 2, 3, 4))));
        System.out.println(toList(s.reverseList(fromArray())));
        System.out.println(toList(s.reverseList(fromArray(7))));
    }
}

Output

[4, 3, 2, 1]
[]
[7]

Time: O(n). Space: O(1).