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

Iterative Method

We will use three pointers current, prev, and nxt to keep track of nodes to update reverse links. First we will initialize two pointers prev as NULL, current as head. Then we will iterate through the linked list. While iterating, we will do the following:

Store the next node using nxt pointer: nxt = current.next.

Now update the next pointer of current to the prev: current.next = prev .

Update prev as current : prev = current and current as nxt current = nxt.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        current = head

        while current:
            nxt = current.next
            current.next = prev
            prev = current
            current = nxt
        

     
        return prev

Time Complexity: O(N)
Space Complexity: O(1)

Recursion

In this approach we reach the last node of the linked list using recursion and then start reversing the linked list. We Divide the list in two parts – first node and rest of the linked list. We call reverseList() for the rest of the linked list and link it to first. Finally, we equate the head pointer to NULL.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        new_head = head
        if head.next:
            new_head = self.reverseList(head.next)
            head.next.next = head
        head.next = None

        return new_head

Time Complexity: O(N)
Space Complexity: O(N), function call stack space.