Skip to content

Instantly share code, notes, and snippets.

@caoxudong
Last active December 19, 2015 13:49
Show Gist options
  • Save caoxudong/5964743 to your computer and use it in GitHub Desktop.
Save caoxudong/5964743 to your computer and use it in GitHub Desktop.
reverse a singly linked list
#!/usr/bin/env python
class Node:
data = None
next = None
def __init__(self,lndata):
self.data=lndata
class List:
size = 0
head = None
tail = None
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def insert(self,value):
newnode = Node(value)
if self.head is None:
self.head = newnode
self.tail = newnode
self.tail.nextnode = None
self.size = self.size + 1
else:
temp_node = self.head
while temp_node.next is not None:
temp_node = temp_node.next
temp_node.next = newnode
self.tail = newnode
self.tail.next = None
self.size = self.size + 1
def toString(self):
if self.size == 0:
print "[]"
else:
temp_node = self.head
print "[",
while (temp_node is not None):
print temp_node.data,
temp_node = temp_node.next
print "]"
def reverse(self):
pCurrent = self.head
pNext = pCurrent.next
pNNext = pNext.next
while pNext.next is not None:
if pCurrent == self.head:
pCurrent.next = None
pNext.next = pCurrent
pCurrent = pNext
pNext = pNNext
pNNext = pNext.next
pNext.next = pCurrent
self.head = pNext
if __name__=='__main__':
link = List()
link.insert(1)
link.insert(2)
link.insert(3)
link.insert(4)
link.toString()
link.reverse()
link.toString()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment