本文适合有一定数据结构基础的人阅读（就是你要懂链表是什么）
在C/C++中，通常采用“指针+结构体”来实现链表；而在Python中，则可以采用“引用+类”来实现链表。
链表L中的每个元素都是一个对象，每个对象有一个关键字key和一个指针：next
题目：单链表倒序，并输出新的链表。
解题思路:
在C的时候我们使用三个指针遍历单链表，逐个链接点进行反转。python也可以采用类似的思路，其实语言并不是很大的关系。
C语言实现参考：
http://blog.csdn.net/Evan123mg/article/details/45725357
代码（包含建立链表、添加节点、打印链表）
class Node:#定义节点
def __init__(self, initdata):
self.__data = initdata
self.__next = None
def getData(self):
return self.__data
def getNext(self):
return self.__next
def setData(self, newdata):
self.__data = newdata
def setNext(self, newnext):
self.__next = newnext
class SinCycLinkedlist:
def __init__(self):
self.head = Node(None)
self.head.setNext(self.head)
def add(self, item):
temp = Node(item)
temp.setNext(self.head.getNext())
self.head.setNext(temp)
def reverse(self):
header =self.head
if header == None or header.getNext().getData() == None:
pass
p1 = header #p1,p2,p3就相当于C语言里的三个指针
p2 = p1.getNext()
while(p2.getData()!=None):
p3 = p2.getNext()
p2.setNext(p1)
p1 = p2
p2 = p3
header.setNext(None)
header = p1
self.head.setData(None)
self.head.setNext(p1)
def print_list(self):
l = []
p =self.head
if p.getData()!= None:
l.append(p.getData())
while (p.getNext().getData()!= None):
p = p.getNext()
l.append(p.getData())
print l
if __name__ == '__main__':
s = SinCycLinkedlist()
s.add(10)
s.add(9)
s.add(8)
s.add(7)
s.add(6)
s.add(5)
s.print_list()
p =s.head
s.reverse()
print "After reverse..."
s.print_list()
运行结果：
[5, 6, 7, 8, 9, 10]
After reverse...
[10, 9, 8, 7, 6, 5]
最近用py比较多，正好拿来复习一下数据结构。其实今天和前天的东西都是我面试时候遇到的题目，对于计算机出身的真是简单得不能再简单，但是对于非科班出身的同学，还是有点难度的，大家面试前一定要提前准备。
我代码可能有bug，因为我的测试数据并不多，但是个人觉得算法要掌握精髓（代码中reverse的部分），甚至说把道理、思路说清楚最好能写出伪代码，面试官也会接纳的。
