python递归&迭代方法实现链表反转
2022-02-21 11:28:09
作者：惊瑟
这篇文章主要介绍了python递归&迭代方法实现链表反转，文章分享一段详细实现代码，需要的小伙伴可以参考一下，希望对你的学习或工作有所帮助
定义链表node结构：
class ListNode:
def __init__(self,data):
self.data = data
self.next = None
将L转化为链表：
def make_list(L):
将L初始化为链表：
head = ListNode(L[0])
cur = head
for i in L[1:]:
cur.next = ListNode(i)
cur = cur.next
return head
遍历链表：
def print_list(head):
cur = head
while cur != None:
print(cur.data,end=' ')
cur = cur.next
递归法 反转链表：
1.明确函数功能，该函数可以将链表反转，并返回一个头节点 2.结束条件：当链表为空或只有一个节点时返回 if head==None or head.next==None:
return head 3.等价条件（缩小范围），对于数组来讲，缩小范围是n——>n-1，对于链表来讲则可以考虑head—— >head.next
reverse = reverse_list(head.next) #假设reverse是head以后的、已经反转过的链表 接下来要做的是将head节点接到已经反转过的reverse上：
tmp = head.next
tmp.next = head
head.next = None
return reverse #返回新的列表 def reverse_list2(head):
#print_list(head)
cur = head
pre = None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
head = pre
return head
if __name__ == '__main__':
L = [3,2,7,8]
head = make_list(L)
正序打印：
print('原始list：')
print_list(head)
print('\n')
反转后打印：
