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 becomes unassociated.

Algorithm

Basic Implementation

basic.f90

program linked_list_reverse
    implicit none
    type :: list_node
        integer :: value
        type(list_node), pointer :: next => null()
    end type list_node

    type(list_node), pointer :: n1, n2, n3, n4, n5
    type(list_node), pointer :: head, prev, cursor, next

    allocate(n5); n5%value = 5; n5%next => null()
    allocate(n4); n4%value = 4; n4%next => n5
    allocate(n3); n3%value = 3; n3%next => n4
    allocate(n2); n2%value = 2; n2%next => n3
    allocate(n1); n1%value = 1; n1%next => n2
    head => n1

    prev => null()
    cursor => head
    do while (associated(cursor))
        next => cursor%next
        cursor%next => prev
        prev => cursor
        cursor => next
    end do
    head => prev
end program linked_list_reverse

The three-pointer loop saves the forward link, flips one next pointer, then advances prev and cursor.

Step 1 - Save the first forward link

prev starts at null, cursor is node(1), and nxt saves node(2).

Step 2 - Flip node(1)

Set node(1).next to prev, making the reversed prefix 1 -> null.

Step 3 - Reversed prefix reaches 3

After three flips, the prefix is 3 -> 2 -> 1 -> null and cursor is node(4).

Step 4 - Done

When cursor reaches null, prev is the new head: 5 -> 4 -> 3 -> 2 -> 1 -> null.

Complexity

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

Implementation notes

Fortran: do not allocate a new list. The reverse happens in place by flipping next pointers. The loop guard associated(cursor) 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.