python递归&迭代方法实现链表反转
作者:惊瑟 时间:2021-05-04 20:42:04
定义链表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))
来源:https://blog.csdn.net/qq_34062683/article/details/121308565
标签:python,递归,迭代,链表,反转
0
投稿
猜你喜欢
Python编程之序列操作实例详解
2023-05-26 16:08:03
Python采集电影评论实战示例
2022-02-25 22:14:37
解析MySQL join查询的原理
2024-01-17 13:28:46
Python 的赋值,浅拷贝和深拷贝详解
2023-08-18 12:28:04
Python中的Numpy 面向数组编程常见操作
2021-08-21 20:31:32
Python列表排序方法reverse、sort、sorted详解
2022-01-06 22:16:39
Python实现爬取逐浪小说的方法
2022-05-26 22:31:29
PHP比你想象的好得多
2023-11-20 09:33:30
Java字符串 正则表达式详解
2023-07-16 12:30:35
Python爬虫实战之虎牙视频爬取附源码
2021-04-02 01:23:27
JS 用6N±1法求素数 实例教程
2024-04-16 08:44:59
python实现带验证码网站的自动登陆实现代码
2021-08-08 19:44:46
Python利用AutoGrad实现自动计算函数斜率和梯度
2023-09-27 22:47:59
基于Python共轭梯度法与最速下降法之间的对比
2022-10-27 06:58:12
如何查看access数据库中各元素的最大容量
2007-08-28 12:44:00
Git的基本操作流程及工作区版本库暂存区的关系
2022-03-10 04:52:42
Python运行出现DeprecationWarning的问题及解决
2022-01-14 05:26:23
python黑魔法之编码转换
2022-08-11 10:03:41
Python程序员鲜为人知但你应该知道的17个问题
2021-06-14 11:37:14
Python闭包与闭包陷阱举例详解
2023-07-05 09:40:10