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
?

递归法  反转链表：

def reverse_list(head):

三要素：

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')
?

反转后打印：

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

反转2：

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

到此这篇关于python递归&迭代方法实现链表反转的文章就介绍到这了,更多相关python链表反转内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

查看更多关于python递归&迭代方法实现链表反转的详细内容...