Linked Structures

Reverse a Singly Linked List

Walk the list with three pointers (prev, cursor, next). Save the forward link, flip cursor.next to point backward, then advance both pointers. The new head is prev when cursor reaches null.

Algorithm

The canonical input is the 5-node list 1 -> 2 -> 3 -> 4 -> 5 -> null. Five rewires produce the reversed list 5 -> 4 -> 3 -> 2 -> 1 -> null.

Basic Implementation

basic.dart 
class ListNode {
  int value;
  ListNode? next;
  ListNode(this.value, this.next);
}

void main() {
  final n5 = ListNode(5, null);
  final n4 = ListNode(4, n5);
  final n3 = ListNode(3, n4);
  final n2 = ListNode(2, n3);
  ListNode? head = ListNode(1, n2);

  ListNode? prev;
  ListNode? cursor = head;
  while (cursor != null) {
    final next = cursor.next;
    cursor.next = prev;
    prev = cursor;
    cursor = next;
  }
  head = prev;
}

Complexity

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

Implementation notes

  • Dart: do not allocate a new list. The reverse happens in place by flipping next pointers. cursor.next is nullable so the loop guard cursor != null doubles as the end-of-list check.
  • The replay shows prev, cursor, next plus the "reversed prefix" / "remaining suffix" view at every step, matching the lesson spec.
three-pointer rewire Each iteration captures the forward link, reverses one edge, then steps.