python 实现单向链表的倒序

本文适合有一定数据结构基础的人阅读（就是你要懂链表是什么）
在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的部分），甚至说把道理、思路说清楚最好能写出伪代码，面试官也会接纳的。