Reverse Linked List

Why it belongs on this sheet

This is the linked-list primitive. Many harder list problems quietly depend on this exact pointer pattern.

Pattern

Prev, current, next

Approach

Walk the list once. Save the next node, reverse the current pointer, then advance the three references.

Java solution

class Solution {
  public ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;

    while (current != null) {
      ListNode next = current.next;
      current.next = previous;
      previous = current;
      current = next;
    }

    return previous;
  }
}

Complexity

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

Interview note

Say the pointer update order clearly. That is usually the only place people slip.