Reverse Linked List

🏠 ⬅️ ➡️

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

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 in the list is the range [0, 5000].
  • -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none
    type :: node
        integer(kind=DP) :: val
        type(node), pointer :: next => null()
    end type
    type(node), pointer :: head => null(), current => null()
    integer :: i

    ! Example 1
    allocate(head)
    head%val = 1
    allocate(current, source=head)
    do i = 2, 5
        allocate(current%next)
        current%next%val = i
        current => current%next
    end do
    call print_list(head)
    call reverse_list(head)
    call print_list(head)
    deallocate(head)

    ! Example 2
    allocate(head)
    head%val = 1
    allocate(current, source=head)
    do i = 2, 2
        allocate(current%next)
        current%next%val = i
        current => current%next
    end do
    call print_list(head)
    call reverse_list(head)
    call print_list(head)
    deallocate(head)

    ! Example 3
    allocate(head)
    call print_list(head)
    call reverse_list(head)
    call print_list(head)
    deallocate(head)

contains

    subroutine print_list(head)
        type(node), pointer :: head
        type(node), pointer :: current

        write (unit=error_unit, fmt='(*(I0, 1X))') 'List:'
        current => head
        do while (associated(current))
            write (unit=error_unit, fmt='(I0, 1X)') current%val
            current => current%next
        end do
        write (unit=error_unit, fmt='()')
    end subroutine

    recursive subroutine reverse_list(head)
        type(node), pointer :: head
        type(node), pointer :: current, previous

        if (.not. associated(head)) then
            return
        end if

        current => head
        previous => null()
        do while (associated(current%next))
            previous => current
            current => current%next
        end do
        current%next => previous
        head => current
    end subroutine

end program
✅ Compiled
✅ Executed
⚠️ Correct 
module reverse_list

implicit none

type :: list_node
    integer :: val
    type(list_node), pointer :: next => null()
end type

contains

recursive subroutine reverse_list_recursive(head)
    type(list_node), pointer :: head
    type(list_node), pointer :: current

    if (.not. associated(head)) then
        return
    end if

    current => head
    call reverse_list_recursive(current%next)
    write (*,*) current%val
    current%next => null()
end subroutine

subroutine reverse_list_iterative(head)
    type(list_node), pointer :: head
    type(list_node), pointer :: current
    type(list_node), pointer :: previous

    if (.not. associated(head)) then
        return
    end if

    current => head
    previous => null()

    do while (associated(current))
        if (.not. associated(current%next)) then
            head => current
        end if
        previous => current
        current => current%next
    end do

    do while (associated(previous))
        write (*,*) previous%val
        previous => previous%next
    end do
end subroutine

end module

program main
    use reverse_list
    implicit none

    ! Example 1
    type(list_node), pointer :: head
    type(list_node), pointer :: current

    allocate(head)
    head%val = 1
    allocate(head%next)
    head%next%val = 2
    allocate(head%next%next)
    head%next%next%val = 3
    allocate(head%next%next%next)
    head%next%next%next%val = 4
    allocate(head%next%next%next%next)
    head%next%next%next%next%val = 5

    call reverse_list_recursive(head)
    call reverse_list_iterative(head)

    ! Example 2
    deallocate(head)
    allocate(head)
    head%val = 1
    allocate(head%next)
    head%next%val = 2

    call reverse_list_recursive(head)
    call reverse_list_iterative(head)

    ! Example 3
    deallocate(head)

    call reverse_list_recursive(head)
    call reverse_list_iterative(head)

end program
🌐 Data from online sources 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev = None
    current = head
    while current is not None:
        next = current.next
        current.next = prev
        prev = current
        current = next
    return prev

The algorithm for reversing a singly linked list involves maintaining three pointers: prev, current, and next. 1. Initialize prev to null and current to the head of the linked list. 2. Iterate through the linked list until current becomes null. 3. In each iteration, set next to be the next node of current. 4. Point the next of current to prev. 5. Move prev one step forward by setting it to current. 6. Finally, move current one step forward by setting it to next. 7. The reversed linked list is obtained when current becomes null, and prev will be the head of the new reversed list.

🌐 Data from online sources 
class ListNode {
public:
    int val;
    ListNode *next;
};

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* current = head;
    ListNode* next = nullptr;
    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

The algorithm for reversing a singly linked list involves maintaining three pointers: prev, current, and next. 1. Initialize prev to null and current to the head of the linked list. 2. Iterate through the linked list until current becomes null. 3. In each iteration, set next to be the next node of current. 4. Point the next of current to prev. 5. Move prev one step forward by setting it to current. 6. Finally, move current one step forward by setting it to next. 7. The reversed linked list is obtained when current becomes null, and prev will be the head of the new reversed list.