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链表反转内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • python算法题 链表反转

    python算法题 链表反转

    链表的反转是一个很常见.很基础的数据结构题,输入一个单向链表,输出逆序反转后的链表,如图:上面的链表转换成下面的链表.实现链表反转有两种方式,一种是循环迭代,另外一种方式是递归. 第一种方式:循坏迭代 循坏迭代算法需要三个临时变量:pre.head.next,临界条件是链表为None或者链表就只有一个节点. # encoding: utf-8 class Node(object): def __init__(self): self.value = None self.next = None de

  • 单链表反转python实现代码示例

    单链表反转python实现代码示例

    单链表的反转可以使用循环,也可以使用递归的方式 1.循环反转单链表 循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可. 代码: class ListNode: def __init__(self,x): self.val=x; self.next=None; def nonrecurse(head): #循环的方法反转链表 if head is None or head.next is None: return head; pre=None; c

  • Python3实现的反转单链表算法示例

    本文实例讲述了Python3实现的反转单链表算法.分享给大家供大家参考,具体如下: 反转一个单链表. 方案一:迭代 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head): """ :type head: ListNod

  • python如何实现单向链表及单向链表的反转

    python如何实现单向链表及单向链表的反转

    链表的定义 链表中的每个节点会存储相邻节点的位置信息,单链表中的每个节点只存储下一关节点的位置信息 单向链表的实现 class ListNode: def __init__(self, val): self.val = val self.next = None 要实现单向链表只需要把几个节点关联起来就可以了,把一个节点的next设置为另一个节点就可以了,例如创建一个A->B->C 的单向链表可以这么写: first_node = ListNode("A") second_n

  • Python实现链表反转的方法分析【迭代法与递归法】

    本文实例讲述了Python实现链表反转的方法.分享给大家供大家参考,具体如下: Python实现链表反转 链表反转(while迭代实现): 链表的反转引入一个cur_node变量,表示当前节点:同时需要引入一个变量new_link表示反转后的新链表:while循环内还需中间变量tmp存放当前节点的后继节点,防止原链表数据丢失. 在while循环内(循环条件为 cur_node !=None,若设置为cur_node.next将导致最后一个节点无法反转到新链表): 首先需要将当前节点的后继节点传递

  • python实现反转部分单向链表

    题目: 给定一个单链表的头指针 head, 以及两个整数 a 和 b,在单链表中反转 linked_list[a-b] 的结点,然后返回整个链表的头指针. 例如: 单链表[1000, 5, 12, 100, 45, 'cecil', 999], a = 4, b = 6, 返回的链表是[1000, 5, 12, 100, 999, 'cecil', 45],也就是说, a 和 b分别为索引值.如果a 和 b 超过了索引范围就返回错误. 代码: 我写的不够简洁,比较繁琐,但是能跑通,繁琐的原因在于

  • 基于Python实现2种反转链表方法代码实例

    题目: 反转一个单链表. 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表.你能否用两种方法解决这道题? 思路: 主要需要注意反转过程中不要丢了节点.可以使用两个指针,也可以使用三个指针. Python解法一: class Solution: def reverseList(self, head): cur, prev = head, None while

  • python如何实现单链表的反转

    这篇文章主要介绍了python如何实现单链表的反转,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码如下 # coding=utf-8 class Node: def __init__(self, data=None, next=None): self.data = data self.next = next def Reserver(link): pre = link cur = link.next pre.next = None whil

  • 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 =

  • Python实现针对给定单链表删除指定节点的方法

    Python实现针对给定单链表删除指定节点的方法

    本文实例讲述了Python实现针对给定单链表删除指定节点的方法.分享给大家供大家参考,具体如下: 题目: 初始化定义一个单链表,删除指定节点,输出链表 下面是具体的实现: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:给定一个单链表删除指定节点 ''' class Node(object): ''''' 节点类 ''' def __init__(self,data): self.num=data self.next=N

  • python算法题 链表反转详解

    python算法题 链表反转详解

    链表的反转是一个很常见.很基础的数据结构题,输入一个单向链表,输出逆序反转后的链表,如图:上面的链表转换成下面的链表.实现链表反转有两种方式,一种是循环迭代,另外一种方式是递归. 第一种方式:循坏迭代 循坏迭代算法需要三个临时变量:pre.head.next,临界条件是链表为None或者链表就只有一个节点. # encoding: utf-8 class Node(object): def __init__(self): self.value = None self.next = None de

  • Python多层嵌套list的递归处理方法(推荐)

    问题:用Python处理一个多层嵌套list ['and', 'B', ['not', 'A'],[1,2,1,[2,1],[1,1,[2,2,1]]], ['not', 'A', 'A'],['or', 'A', 'B' ,'A'] , 'B'] 需求1)如何展开成一层? 需求2)如何删除重复的元素? 包括重复的list, 要考虑子list的重复元素删除后造成的子list重复 #!/usr/bin/env python # -*- coding: utf-8 -*- def unilist(l

  • python二分查找算法的递归实现方法

    本文实例讲述了python二分查找算法的递归实现方法.分享给大家供大家参考,具体如下: 这里先提供一段二分查找的代码: def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: found = True else: if ite

  • Python递归遍历列表及输出的实现方法

    本文实例讲述了Python递归遍历列表及输出的实现方法.分享给大家供大家参考.具体实现方法如下: def dp(s): if isinstance(s,(int,str)): print(s) else: for item in s: dp(item) l=['jack',('tom',23),'rose',(14,55,67)] dp(l) 运行结果如下: jack tom 23 rose 14 55 67 希望本文所述对大家的Python程序设计有所帮助.

  • python递归删除指定目录及其所有内容的方法

    实例如下: #! /usr/bin/python # -*- coding: utf-8 -*- import os def del_dir_tree(path): ''' 递归删除目录及其子目录, 子文件''' if os.path.isfile(path): try: os.remove(path) except Exception, e: #pass print e elif os.path.isdir(path): for item in os.listdir(path): itempa

随机推荐