educative.io

Educative

Simpler approach (C++)

Another method, which I find more clear, is to build a new list and prepend nodes one by one to it. It has the same time and space complexities, but it’s easier to reason through.

static ListNode *reverse(ListNode *head) {
    ListNode dummy(0);

    while (head != nullptr) {
      auto next = head->next;
      head->next = dummy.next;
      dummy.next = head;
      head = next;
    }

    return dummy.next;
}

Yes, this is correct. But if you are not allowed to use any extra space, then this approach won’t work.

@Naima_Ali, this does not count as extra space. Space complexity remains O(1). Nodes are just moved.
In this regard it’s no different than the solution used in the course.