206. Reverse Linked List

Question

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]

Solution 1: Recursive

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        revHead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
            
        return revHead

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

Solution 2: Iterative

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        
        pre = None
        while(head):
            nxt = head.next
            head.next = pre
            pre = head
            head = nxt
            
        return pre

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

Reference

N/A

Follow-up: Reverse Linked List II

TODO

Time Complexity: O()
Space Complexity: O()