Linked lists · stretch

Reverse a linked list

Write reverse(head) that reverses the list by relinking the existing nodes — no new Nodes — and returns the new head.

You need three names: the node before, the current node, and the one after (so you do not lose the rest of the list when you change current.next).

right answers
arguments left as they should be
without build

Already written for you — you can use these

1class Node:
2    def __init__(self, value, next=None):
3        self.value = value
4        self.next = next
5 
6def build(values):
7    head = None
8    for v in reversed(values):
9        head = Node(v, head)
10    return head

def reverse(head):
    new_head = None
    node = head
    while node is not None:
        new_head = Node(node.value, new_head)
        node = node.next
    return new_head

Run adds head = head.next after your code, to try it.

Stuck on the idea rather than the code? The Linked lists lesson walks through it.