本文实例为大家分享了python递归实现链表快速倒转的具体代码,供大家参考,具体内容如下
案例:实现如下链表进行倒转
源代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
''' Node 用于表示队列中的节点;它包含两个域。 val 表示节点的值。 next指向下一个节点 ''' #定义链表的数据结构 class Node: def __init__( self ,val): self . next = None self .val = val class ListUtility: #生成一个用来操作的链表 def __init__( self ): self .head = None self .tail = None pass def createList( self ,nodeNum): if nodeNum < = 0 : return None head = None val = 0 node = None while nodeNum > 0 : #如果head指针为空,代码先构造队列头部,如果不为空,代码构造节点对象,然后用上一个节点的next指针指向当前节点,从而将多个节点串联成队列。 if head is None : head = Node(val) node = head else : node. next = Node(val) node = node. next self .tail = node val + = 1 nodeNum - = 1 self .head = head return head def printList( self ,head): while head is not None : print ( "{0}->" . format (head.val),end = " " ) head = head. next print ( "null" ) class ListReverse: def __init__( self , head): self .listHead = head self .newHead = None def recursiveReverse( self , node): #如果队列为空或者只有一个节点,那么队列已经倒转完成 if node is None or node. next is None : self .newHead = node return node ''' 如果队列包含多个节点,那么通过递归调用的方式,先把当前节点之后所有节点实现倒转, 然后再把当前节点之后节点的next指针指向自己从而完成整个列表所有节点的导致 ''' head = self .recursiveReverse(node. next ) head. next = node node. next = None return node def getReverseList( self ): ''' listHead是原队列头节点,执行recursiveReverse后newHead指向新列表的头结点,它 对应的其实是原列表的尾节点,而head指向新列表的尾节点 ''' self .recursiveReverse( self .listHead) return self .newHead utility = ListUtility() head = utility.createList( 10 ) utility.printList(head) #执行倒转算法,然后再次打印队列,前后对比看看导致是否成功 reverse = ListReverse(head) utility.printList(reverse.getReverseList()) |
运行结果:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/qq_44176343/article/details/118655436