206. Reverse Linked List.md

206. Reverse Linked List (Easy)

[tag] two pointers, recursion

Method 1. Two pointers and iteratively

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # use two pointers: prev and cur
        prev, cur = None, head
        while cur:
            cur_next = cur.next
            cur.next = prev
            prev = cur
            cur = cur_next
        return prev

Method 2. Recursion

• fixed the first pointer and recursive reverse the latter ones

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # this is only for storing the new head.
        new_head = head
        if not head:
            return None
        if head.next:
            new_head = self.reverseList(head.next)
            head.next.next = head
        head.next = None
        return new_head