Reverse Linked List

Example 1

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Diagram

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next: ListNode = None

    def __repr__(self):
        return self.val

    def print(self):
        print(self.val)
        if self.next:
            self.next.print()

def reverse_list(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    node = reverse_list(head.next)
    head.next.next = head
    head.next = None
    return node


def reverse_list_2(head: ListNode) -> ListNode:
    prev = None
    current = head
    while current:
        temp_next = current.next
        current.next = prev
        prev = current
        current = temp_next
    return prev

print("Before reverse")
node1 = ListNode(1)
node1.next = ListNode(2)
node1.next.next = ListNode(3)
node1.print()
print("After reverse")
new_node = reverse_list_2(node1)
new_node.print()

Before reverse
1
2
3
After reverse
3
2
1