206. Reverse Linked List

Description:

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

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

'''
[1] iterative)

code::
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    prev=None
    cur=head
    next=cur
    while cur:
        next=cur.next
        cur.next=prev
        prev=cur
        cur=next
    return prev

-T/C: O(n)
-S/C: O(1)
'''
'''
[1] recursive)

code::
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head:
        return head
    return self.reverse(None,head)

def reverse(self,prev,cur):
    if not cur:
        return prev
    next=cur.next
    cur.next=prev
    prev=cur
    cur=next
    return self.reverse(prev,cur)

-T/C: O(n)
-S/C: O(n)
'''
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        return self.reverse(None,head)
        
    def reverse(self,prev,cur):
        if not cur:
            return prev
        next=cur.next
        cur.next=prev
        prev=cur
        cur=next
        return self.reverse(prev,cur)