Python ProgrammingLevel: Intermediatepython

Reverse a Singly Linked List in Python: Worked Example

Prepared by the Assignment Achievers computer science team.

Free Educational Resource

Problem Statement / Assignment Scope

Given the `head` node of a singly linked list, reverse the list in place and return the new head. Use O(n) time and only O(1) extra space.

Prerequisites: Python classes and objects, and how variables hold references to objects.

Step-by-Step Worked Solution

1. Three pointers

Instead of building a new list, we turn each arrow around as we walk along. That needs three references: previous (the part already reversed), current (the node being changed) and following (the rest of the list).

Save current.next in following first, or the rest of the list is lost.
Point current.next back at previous.
Move previous and current forward one node and repeat.

2. Tracing 1 → 2 → 3

After the first pass, 1 points to nothing. After the second, 2 points to 1. After the third, 3 points to 2, current becomes None and the loop stops, returning 3 as the new head.

3. Edge cases

An empty list (head is None) skips the loop and returns None. A single node is returned unchanged. Both are worth including in your tests.

solution.pypython

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next


def reverse(head: Node | None) -> Node | None:
    """Reverse a singly linked list in place. Time O(n), extra space O(1)."""
    previous = None
    current = head

    while current:
        following = current.next   # remember the rest of the list
        current.next = previous    # point this node backwards
        previous = current         # move both pointers one step on
        current = following

    return previous  # the old tail is the new head


def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out


print(to_list(reverse(Node(1, Node(2, Node(3))))))  # [3, 2, 1]

Key Takeaways & Core Principles

Reversing in place needs no new nodes, so extra memory stays at O(1).
Always save the next node before you change a pointer.
Test the empty list and the single-node list as well as a normal case.

Frequently Asked Questions

What are the time and space costs?

O(n) time, because every node is visited once, and O(1) extra space, because only three reference variables are used however long the list is.

Academic References & Standards

[1]Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley. Source Link

Help With Your Own Task

Got a Similar Question for Your Course?

Send it to an Assignment Achievers expert. You'll get an original answer that follows your brief and rubric, the working shown step by step, and a free originality report.