206. Reverse Linked List

Problem¶

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

Constraints:

The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Solve¶

Stack¶

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

        p = head
        while p:
            queue.append(p)
            p = p.next
        result = None
        p = None
        while queue:
            if result is None:
                result = queue.pop()
                p = result
            else:
                p.next = queue.pop()
                p = p.next
        if p:
            p.next = None

        return result

Recursion¶

We start with this order: go to the node first, then process our current node value (using print as a place holder)

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

        def helper(node):
            if node:
                helper(node.next)
                print(node.val)

        helper(head)
        return None

Now instead of printing, we adding node to result instead. Here I using p as a temporary storing the end of result linked list of link list for O(1) time insert.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        self.result = None
        self.p = None

        def helper(node):
            if node:
                helper(node.next)
                if self.result is None:
                    self.result = node
                    self.p = self.result
                else:
                    self.p.next = node
                    self.p = self.p.next
                    self.p.next = None

        helper(head)
        return self.result

Last update : September 23, 2023
Created : August 16, 2023