15. [Linked List]: reverse list

206. Reverse Linked List

Easy

18.3K

339

Companies

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

Example 1:

!https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg

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

Example 2:

!https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg

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

Example 3:

Input: head = []
Output: []

Constraints:

• The number of nodes in the list is the range [0, 5000].

• 5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Accepted

3.1M

Submissions

4.3M

Acceptance Rate

Count Primes - LeetCodeLeetCode

Iteration

time: O(N)

space: O(1)

var reverseList = function(head) {
    if (head === null || head.next === null) 
        return head;
    
    let prev = null;
    let curr = head;
    while (curr !== null) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
};

Recursive

time: O(N)

space: O(N)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */

var reverseList = function(head) {
    if (head === null || head.next === null) {
        return head;
    }

    const prev = new ListNode(-1);
    reverse(prev, head);
    
    return prev.next;
};

function reverse(prev, node) {
    if (node.next === null) {
        prev.next = node;
        return node;
    }

    const reversed = reverse(prev, node.next);
    reversed.next = node;
    node.next = null;

    return node;
}