python中如何用递归与迭代方法实现链表反转(python,开发技术)

定义链表node结构：

classListNode:def__init__(self,data):self.data=dataself.next=None

将L转化为链表：

defmake_list(L):

将L初始化为链表：

head=ListNode(L[0])cur=headforiinL[1:]:cur.next=ListNode(i)cur=cur.nextreturnhead

遍历链表：

defprint_list(head):cur=headwhilecur!=None:print(cur.data,end='')cur=cur.next

递归法 反转链表：

defreverse_list(head):

三要素：

• 1.明确函数功能，该函数可以将链表反转，并返回一个头节点

• 2.结束条件：当链表为空或只有一个节点时返回

ifhead==Noneorhead.next==None:returnhead

• 3.等价条件（缩小范围），对于数组来讲，缩小范围是n——>n-1，对于链表来讲则可以考虑head——

>head.nextreverse=reverse_list(head.next)#假设reverse是head以后的、已经反转过的链表

接下来要做的是将head节点接到已经反转过的reverse上：

tmp=head.nexttmp.next=headhead.next=Nonereturnreverse#返回新的列表

迭代法：

defreverse_list2(head):#print_list(head)cur=headpre=Nonewhilecur:tmp=cur.nextcur.next=prepre=curcur=tmphead=prereturnheadif__name__=='__main__':L=[3,2,7,8]head=make_list(L)

正序打印：

print('原始list：')print_list(head)print('\n')

反转后打印：

revere=reverse_list(head)print('反转一次的list：')print_list(revere)print('\n')

反转2：

print('headis')print_list(head)#发现此时head节点变成了最后一个节点，说明函数是对head这个实例直接作用的print('\n')#print('revereis')#print_list(revere)#print('\n')print('反转两次的list：')print_list(reverse_list2(revere))