Reverse Linked List

本题是反转一个单链表，题目提示使用迭代和递归两种方式，属于比较基础的题目。

一,迭代方式：总体思路是从左到右遍历链表结点，依次反转连接关系。每次处理相邻的两个结点，从<None,head>这一对开始。代码如下：

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev=None
        while head:
            next = head.next
            head.next=prev
            prev = head
            head = next
        return prev

代码中prev为每次结点对的先序结点，当head为None时，prev为目前链表的末结点，所以返回prev. 注意每次需要反转一个连接,所以每次的节点对之间有一个节点的重合.另外头节点的next一定要置为0,不然会形成回环.

二，递归方式,假设前面已经反转，现在这一步要怎么处理。一定要掌握，被腾讯问到。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        return self.helper(None, head)
        
    def helper(self, pre, cur):
        if not cur:
            return pre
        next = cur.next #the next cur node
        cur.next = pre # cur is the next pre node
        return self.helper(cur, next)