SOLVED: LeetCode: 206. Reverse Linked-List

@iamserda

Published in

SWELOGIC

3 min readFeb 12, 2024

A beginner-friendly solution with a detailed code-walkthrough.

https://techbum.io/reversing-linked-list-pattern

Intuition

Upon seeing the problem of reversing a singly-linked list, the immediate thought is how to reorient the arrows (pointers) so that they point backward, making the last node the new head. The main challenge is doing this without losing track of the nodes as we change their pointers, ensuring that each node points to its predecessor instead of its successor.

Approach

The solution employs a straightforward yet effective method using three pointers: left_ptr, temp_ptr, and right_ptr. Initially, left_ptr acts as a placeholder for the new reversed list, starting as None since the new head's previous node does not exist. temp_ptr starts at the head of the original list, and right_ptr is used to keep track of the list's remainder as we iterate. The process involves pointing the current node (temp_ptr) to left_ptr, effectively reversing the link, and then advancing left_ptr and temp_ptr forward (in the original list's perspective) until all nodes have been reversed. Finally, head is updated to left_ptr, which points to the new head of the reversed list.

Complexity

Time complexity: O(n): Each node in the list is visited exactly once to reverse its pointer, leading to a linear time complexity proportional to the length of the list.
Space complexity: O(1): The space used does not depend on the size of the input list. Only a fixed number of pointers (left_ptr, temp_ptr, right_ptr) are used regardless of the list's length, ensuring a constant space complexity.

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = nextclass Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        if not head.next:
            return head
        left_ptr = None
        temp_ptr = head
        right_ptr = temp_ptr
        while temp_ptr:
            right_ptr = right_ptr.next
            temp_ptr.next = left_ptr
            left_ptr = temp_ptr
            temp_ptr = right_ptr
        head = left_ptr
        return head

Code Walkthrough:

Let’s walk through the code step by step to understand how it reverses a singly-linked list.

Step 1: Initial Check

if not head:
    return head
if not head.next:
    return head

First, the code checks if the list is empty (head is None) or contains only one element (head.next is None). In either case, the list is returned as is because an empty list or a single-element list is already reversed in itself.

Step 2: Initialization of Pointers

left_ptr = None
temp_ptr = head
right_ptr = temp_ptr

Three pointers are introduced:
left_ptr starts as None and will eventually point to the new head of the reversed list.
temp_ptr points to the current node being processed, starting with head.
right_ptr is used to track the next node in the list as we're reversing the links, initially set to the same node as temp_ptr.

Step 3: Reversing the Links

while temp_ptr:
    right_ptr = right_ptr.next  # Move right_ptr to the next node.
    temp_ptr.next = left_ptr    # Reverse the current node's pointer.
    left_ptr = temp_ptr         # Move left_ptr to the current node.
    temp_ptr = right_ptr        # Proceed to the next node to process.

The loop continues until temp_ptr becomes None, indicating the end of the list has been reached.
Inside the loop:
right_ptr is advanced to the next node. This is crucial because the operation temp_ptr.next = left_ptr will lose the original next node of temp_ptr.
The current node’s next pointer (temp_ptr.next) is redirected to left_ptr, effectively reversing the link. For the first iteration, this sets the original head's next to None, starting the new tail of the reversed list.
left_ptr is then moved forward to temp_ptr, marking the current node as the new head of the partially reversed list so far.
Finally, temp_ptr moves forward to right_ptr, preparing the next node for processing.

Step 4: Finalizing the New Head

head = left_ptr
return head

After the loop, left_ptr points to the new head of the reversed list (the original list's tail). The original head variable is updated to point to left_ptr.
The new head of the reversed list is returned.

This method efficiently reverses the linked list in-place, utilizing a constant amount of extra space (for the pointers) and making a single pass through the list, thus achieving O(n) time complexity and O(1) space complexity.