DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 59: Python Reverse Singly Linked List, Master the Iterative Pointer Flip Technique for O(n) Reversal

#challenge #python #algorithms #datastructures

Welcome to Day 59 of the #80DaysOfChallenges journey! This intermediate challenge implements reversing a singly linked list using an iterative pointer manipulation approach, reassigning 'next' pointers in a three-variable dance to flip the list in O(n) time with O(1) space. It includes a Node class, builder for list creation from arrays, printer for visualization, and main for interactivity, making it a complete package for linked list fundamentals. If you're gearing up for interviews where "reverse linked list" is a staple (LeetCode #206), or practicing data structure mutations, this "Python reverse linked list" script demonstrates a method that's efficient, in-place, and essential for understanding pointer logic without recursion's stack overhead.

💡 Key Takeaways from Day 59: Linked List Reversal Function

This task features a Node class for structure, builder and printer helpers for usability, and the core reversal function with pointer updates. It's a classic in-place reversal: traverse while flipping links. We'll detail: Node class and builder for list creation, reversal with three pointers, and printer with main interactivity.

1. Node Class and Builder: Simple List Construction

The Node class defines the basic structure:

class Node:
    """Simple singly linked list node."""
    def __init__(self, value: int):
        self.value = value
        self.next = None
Enter fullscreen mode Exit fullscreen mode

Standard setup with value and next pointer.

The build_linked_list creates from array:

def build_linked_list(values: list[int]) -> Node:
    """Build a linked list from a list of integers and return the head."""
    if not values:
        return None

    head = Node(values[0])          # create the first node using the first list element
    curr = head                     # pointer 'curr' will track the end of the list as we build

    for v in values[1:]:            # iterate through all remaining values
        curr.next = Node(v)         # create a new node and attach it to the current node
        curr = curr.next            # move 'curr' forward to the newly created node

    return head                     # return the head of the fully built linked list
Enter fullscreen mode Exit fullscreen mode

Loops to chain nodes, O(n) time. Handles empty as None.

2. Reversal Function: Three-Pointer Flip

The reverse_list flips pointers iteratively:

def reverse_list(head: Node) -> Node:
    """
    Reverse a linked list iteratively.
    Returns the new head of the reversed list.
    """
    prev = None
    current = head

    while current is not None:
        nxt = current.next        # store next
        current.next = prev       # reverse pointer
        prev = current            # move prev forward
        current = nxt             # move current forward

    return prev
Enter fullscreen mode Exit fullscreen mode

The classic three-pointer dance: nxt temps next, flip to prev, shift prev/current. For 1->2->3: becomes 3->2->1, prev=3 as new head. In-place, no extra space.

3. Printer and Main: Visualization and Input

The print_linked_list displays:

def print_linked_list(head: Node) -> None:
    """Print linked list values cleanly."""
    curr = head   # start traversing from the head node
    nodes = []    # store node values as strings for pretty output

    # continue until the end of the list
    while curr is not None:
        nodes.append(str(curr.value))  # append the current node's value
        curr = curr.next    # move to the next node in the list

    # print values joined with arrows
    print(f"Linked List: {' -> '.join(nodes)}")
Enter fullscreen mode Exit fullscreen mode

Collects values, joins with arrows for "1 -> 2 -> 3".

Main handles input:

raw = input("Enter numbers for the linked list (space-separated): ").strip()

if raw == "":    # check for empty input
    print("No input provided. Exiting.")   # notify user and stop
    return

# split input into numbers and convert to integers
nums = list(map(int, raw.split())) 

# construct a linked list from the input numbers
head = build_linked_list(nums)    
print_linked_list(head)           # display the original list

# reverse the linked list using pointer manipulation
reversed_head = reverse_list(head)
print_linked_list(reversed_head)   # display the reversed list
Enter fullscreen mode Exit fullscreen mode

Parses space-separated ints, builds, prints original/reversed. User-friendly.

🎯 Summary and Reflections

This linked list reversal shows pointer mastery in action, flipping with temp nxt. It reinforced:

  • Three-pointer pattern: Nxt, flip, shift – core for in-place ops.
  • In-place efficiency: O(n) time, O(1) space.
  • Builder/printer helpers: Make lists testable.

Reflections: Recursion possible but stack risky for long lists. Iterative safer.

Advanced Alternatives: Recursive reverse. Head recursion for print. Your linked list tip? Share!

🚀 Next Steps and Resources

Day 59 honed pointer skills, prepping for list algos. In #80DaysOfChallenges? Doubly linked? Post!

Top comments (0)