Build a Linked ListStep 2 of 5

Reverse the List

12345

Step 2: Reverse the List

Reversing a singly linked list is a rite of passage. You cannot walk backwards, so you flip each next pointer as you go.

Implement reverse(head) which returns the new head of the reversed list. Do it iteratively with three references: the previous node, the current node, and a saved next node so you do not lose the rest of the chain when you flip a pointer.

An empty list (head is None) should return None.

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


def from_list(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head


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


def reverse(head):
    """Reverse the list in place and return the new head node."""
    # TODO: walk the list flipping each next pointer, tracking prev and current
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step