单链表反转
唯一就是有一处笔误。 3.4.4 两个链表操作/链表反转 书中代码是：
代码语言：javascript复制def rev(self):
p = None
while self._head is not None:
q = self._head
self._head = q.next # 摘下原来的原结点
q._next = p
p = q # 将刚摘下的结点加入 p 引用的结点序列
self._head = p # 反转后的结点序列已经做好，重置表头链接其中倒数第三行的 ._next 应该改为 .next，因为结点类 LNode 中类属性是.next。
q.next = p如果把其中的 p 变量更名为 tmp_list_head，把 q 改为 sliced_node可能更能理解。
完整的程序，包括测试如下：
代码语言：javascript复制# coding:utf8
class LinkedListUnderflow(ValueError):
pass
class LNode(object):
def __init__(self, elem, next_=None):
self.elem = elem
self.next = next_
class LList(object):
def __init__(self):
self._head = None
def is_empty(self):
return self._head is None
def prepend(self, elem):
self._head = LNode(elem, self._head)
def pop(self):
if self._head is None:
raise LinkedListUnderflow("in pop")
e = self._head.elem
self._head = self._head.next
return e
def append(self, elem):
if self._head is None:
self._head = LNode(elem)
return
p = self._head
while p.next is not None:
p = p.next
p.next = LNode(elem)
def pop_last(self):
if self._head is None:
raise LinkedListUnderflow
p = self._head
if p.next is None:
e = p.elem
self._head = None
return e
while p.next.next is not None:
p = p.next
e = p.next.elem
p.next = None
return e
def rev(self):
tmp_list_head = None
while self._head is not None:
sliced_node = self._head
self._head = self._head.next
sliced_node.next = tmp_list_head
tmp_list_head = sliced_node
self._head = tmp_list_head
def elements(self):
p = self._head
while p is not None:
yield p.elem
p = p.next
def main():
lst = LList()
for i in range(10):
lst.append(i)
print "original linked list:"
for i in lst.elements():
print i
print '-' * 25
print "reserved linked list:"
lst.rev()
for i in lst.elements():
print i
if __name__ == '__main__':
main()
