Problem Statement

Description

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

Examples

Example 1:

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

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints

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

Key Insights

In order to reverse a singly linked list iteratively, you need to use three pointers: prev, curr and next. The following algorithm can be used:

  1. Advance the next pointer to the next node
  2. Reverse the curr.next pointer so that it points back to prev
  3. Advance the prev pointer to curr
  4. Advance the curr pointer up to next
flowchart LR z((prev=Ø))-.-a((curr=1))-.-b((next=2))-->c((3))-->d((4))-->e((5)) a-->z

In order to reverse a singly linked list recursively, we will need to be very careful to ensure that we don’t end up with any cycles. The following algorithm can be used:

  1. For each recursive call, check if head or head.next is None and return head if either are. If head is None, we know that we don’t have a linked list and we need to exit. If head.next is None, we know that we have either reached the end, or we have successfully broken the link between the head and the next node.
  2. Once the previous two conditions have passed, we will recursively call reverseList(head.next) to drill down to the end of the list. Once we reach the end, (head.next).next will be None, and it will return return head.next up one stack frame.
  3. We will then reverse the pointer head.next.next = head
  4. We will set head.next = None to avoid cycles
  5. Finally, we will return the node from the previous call up the call stack. Once we return back to the first call, the returned result will be the original tail node that is now the new head node.

Python Solution

Iterative Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

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

        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next

        return prev

Recursive Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        else:
            node = self.reverseList(head.next)
            head.next.next = head
            head.next = None

            return node