Skip to content

Instantly share code, notes, and snippets.

@dwf
Created April 24, 2010 04:35
Show Gist options
  • Save dwf/377466 to your computer and use it in GitHub Desktop.
Save dwf/377466 to your computer and use it in GitHub Desktop.
And *that* is how to reverse a linked list. I'm an idiot for messing this up.
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
def __str__(self):
"""Return a string representation of the list starting here."""
values = []
curr = self
while curr is not None:
print repr(curr)
values.append(str(curr.value))
curr = curr.next
return ",".join(values)
def reverse(head):
"""reverse a linked list in-place and return the new head."""
curr = head.next
prev = head
prev.next = None # Break the link between the head and whatever's after it.
while curr is not None:
# Retain a reference to whatever curr points to now.
tmp = curr.next
# make curr point at the thing before it.
curr.next = prev
# move everybody forward.
prev = curr
curr = tmp
# when this loop terminates curr should be None but prev
# will be the last element, now the first.
return prev
if __name__ == "__main__":
# Some demo code.
a = Node(4)
a.next = Node(5)
a.next.next = Node(6)
a.next.next.next = Node(7)
print a
b = reverse(a)
print b
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment