逆置链表(python)

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

链表的数据结构定义

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        #头插
        p = None #新建的结点,为头结点
        h = None #暂存的结点
        while(head):
            h = head
            head = head.next #向下遍历
            h.next = p #插入到头部
            p = h
        return p

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if (not head or head.next is None ): #空链表或者单元素链表
            return head
        # #递归结束条件
        t = self.reverseList(head.next) #假设剩下的F(N-1)已经解决
        head.next.next = head #只需要把当前的元素与接着的元素反转
        head.next = None #释放next 域
        return t