Reverse Linked List

Reverse Linked List (Leetcode 206)

There are two ways to reverse a linked list, i.e., iteratively and recursively.

The key idea of recursive approach is to firstly traverse to the end of the linked list, then reverse the pointers while backtracking.

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

        if head is None or head.next is None:
            return head

        last = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return last

The key idea of iterative approach is to maintain three pointers, i.e., prev, cur, and nxt. We reverse the pointers iteratively.

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

        if head is None or head.next is None:
            return head

        prev, cur, nxt = None, head, head.next


        while cur:
            cur.next = prev

            prev = cur
            cur = nxt
            if nxt is not None:
                nxt =  nxt.next

        return prev