LeetCode0206.反向链表【易】【Python】【链表】问题LeetCode反向一个单链表。例子：输入：1->2->3->4->5->NULLOutput:5->4->3->2->1->NULLFollowup:链表可以迭代或递归地反转。你能同时实施吗？单向链表。示例：输入：1->2->3->4->5->NULL输出：5->4->3->2->1->NULL进阶：可以迭代或递归地反转链表。你能用两种方法解决这个问题吗？思路解决方案普通数组的栈模拟栈实现链表反转的时间复杂度：O(n)，n为链表的长度。空间复杂度：O(n)，其中n是链表的长度。Python3代码#单链表的定义。#classListNode:#def__init__(self,x):#self.val=x#self.next=Noneclass解决方案：defreverseList(self,head:ListNode)->ListNode:#解决方法一：Listpos=headnewList=[]whilepos:newList.insert(0,pos.val)pos=pos.nextpos=headfor_innewList:pos.val=_pos=pos.nextreturnhead解决方法两个双指针使用cur和pre双指针实现反向链表。你可以在纸上手绘，你可以理解这个过程。时间复杂度：O(n)，其中n是链表的长度。空间复杂度：O(1)Python3code#Definitionforsingle-linkedlist.#classListNode:#def__init__(self,x):#self.val=x#self.next=Noneclass解决方案：defreverseList(self,head:ListNode)->ListNode:#解决方法二：两点cur,pre=None,headwhilepre:pos=pre.nextpre.next=curcur=prepre=posreturncur解决方法三递归直接使用递归实现倒置链接列表。时间复杂度：O(n)，其中n是链表的长度。空间复杂度：O(1)Python3code#Definitionforsingle-linkedlist.#classListNode:#def__init__(self,x):#self.val=x#self.next=Noneclass解决方案：defreverseList(self,head:ListNode)->ListNode:#方案三：递归ifnotheadornothead.next:returnheadpos=head.nextnewList=self.reverseList(pos)head.next=Nonepos.next=headreturnnewList代码地址github关联
