LintCode 35 题
给出一个链表：1->2->3->null，这个翻转后的链表为：3->2->1->null
使用 python 语言实现：
#coding:utf-8
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
class Solution:
"""
采用循环的方法反转链表
@param: head: n
@return: The new head of reversed linked list.
"""
def reverse(self, head):
if head is None or head.next is None:
return head
cur = head.next
head.next = None
while cur:
cur_next = cur.next
cur.next = head
head = cur
cur = cur_next
return head # new head
"""
采用递归的方法反转链表
时间复杂度 O(n)
head 为原链表的头结点，new_head 为反转后链表的头结点
"""
def reverse_recursive(self, head):
if head is None or head.next is None:
return head
else:
new_head = self.reverse_recursive(head.next)
head.next.next = head
head.next = None
return new_head
# 测试代码1，建立链表：1->2->3->None
head = ListNode(1)
p1 = ListNode(2)
p2 = ListNode(3)
head.next = p1
p1.next = p2
# 输出链表：3->2->1->None
s1 = Solution().reverse(head)
while s1:
print s1.val
s1 = s1.next
# 测试代码2，建立链表：1->2->3->None
head = ListNode(1)
p1 = ListNode(2)
p2 = ListNode(3)
head.next = p1
p1.next = p2
# 输出链表：3->2->1->None
s2 = Solution().reverse_recursive(head)
while s2:
print s2.val
s2 = s2.next
图解递归方法：
