python中如何用递归与迭代方法实现链表反转

这篇文章主要讲解了"python中如何用递归与迭代方法实现链表反转"，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习"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中如何用递归与迭代方法实现链表反转这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是，小编将为大家推送更多相关知识点的文章，欢迎关注！