python 递归解法

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
'''
递归：
1.开始状态
       |pHead|--->|pHead.next|--> ……

2.递归：假设pHead.next之后的结点已经反转则如下：
           ___________________      newHead=self.ReverseList(pHead.next)    
          |                   ↓                     | 
      |pHead|     None <--|pHead.next| <-- …… <--|newHead|  

  接下来只需进行如下操作：
       pHead.next指向pHead，
       pHead指向None 就完成了最后一步操作：
                                    newHead=self.ReverseList(pHead.next)    
                                                     |
      None <--|pHead|  <--|pHead.next| <-- …… <--|newHead|  

  最后返回整个链表的新表头即可

3.加上递归结束条件
    当pHead为None时直接返回None 当我们pHead.next为None时 返回pHead就行
'''
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if not pHead or not pHead.next:
               return  pHead
        newHead=self.ReverseList(pHead.next)
        pHead.next.next=pHead
        pHead.next=None
        return newHead