Skip to content

206. Reverse Linked List

Summary

Solution Approach Explanation (1-minute) Time Complexity Space Complexity
Iterative Use three pointers (prev, curr, next) to reverse links while traversing \(O(n)\) \(O(1)\)
Recursive Recursively reverse from tail, then fix current node's links \(O(n)\) \(O(n)\)

Implementation

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

        prev = None
        curr = head

        while curr != None:
            nxt = curr.next

            curr.next = prev

            prev = curr
            curr = nxt

        return prev

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

        if head == None:
            return None

        new_head = head
        if head.next != None:
            new_head = self.reverseList(head.next)
            head.next.next = head
        head.next = None
        return new_head
```