3. Reverse Linked List

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

Example 1

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

Example 2

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

Example 3

Input: head = []
Output: []

Constraints

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

💡 Hint 1

Walk the list once, flipping each next pointer to point backwards.

💡 Hint 2

You need three references: previous, current and the saved next node.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Iterate with prev = null and curr = head. Save curr.next, point curr.next back at prev, then advance both. When curr falls off the end, prev is the new head. (A recursive version works too but uses O(n) stack.)

Time O(n)Space O(1)

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

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

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

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit