I have a singly linked list and want to reverse it without allocating a new list. My attempt loses the rest of the list after the first node:
while node:
node.next = prev
prev = node
node = node.nextI have a singly linked list and want to reverse it without allocating a new list. My attempt loses the rest of the list after the first node:
while node:
node.next = prev
prev = node
node = node.nextYou overwrite node.next before saving it. Keep a reference to the next node first:
def reverse(head):
prev = None
node = head
while node:
nxt = node.next
node.next = prev
prev = node
node = nxt
return prevThis runs in O(n) time and O(1) extra space.
A recursive version also works, but it uses O(n) stack space and can hit the recursion limit on long lists.