NC78 反转链表 python

描述
输入一个长度为n链表，反转链表后，输出新链表的表头。

数据范围： n ≤ 1000 n leq 1000 n≤1000
要求：空间复杂度 O ( 1 ) O(1) O(1)，时间复杂度 O ( n ) O(n) O(n)

示例1

输入：{1,2,3}
返回值：{3,2,1}

示例2

输入：{}
返回值：{}
说明：空链表则输出空

Python实现

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        # 递归实现
        if not pHead or not pHead.next:
            return pHead
        else:
            newHead = self.ReverseList(pHead.next)
            pHead.next.next=pHead
            pHead.next=None
            return newHead
        # 非递归实现
#         if pHead is None:
#             return pHead
#         last = None  #指向上一个节点
#         while pHead:
#             # 先用tmp保存pHead的下一个节点的信息，
#             # 保证单链表不会因为失去pHead节点的next而就此断裂
#             tmp = pHead.next
#             # 保存完next，就可以让pHead的next指向last了
#             pHead.next = last
#             # 让last，pHead依次向后移动一个节点，继续下一次的指针反转
#             last = pHead
#             pHead = tmp
#         return last

参考：
https://www.cnblogs.com/tianqizhi/p/9673894.html