定义链表node结构：
|
1
2
3
4
5
|
class ListNode: def __init__(self,data): self.data = data self.next = None |
将L转化为链表：
|
1
|
def make_list(L): |
将L初始化为链表：
|
1
2
3
4
5
6
7
|
head = ListNode(L[0]) cur = head for i in L[1:]: cur.next = ListNode(i) cur = cur.next return head |
遍历链表：
|
1
2
3
4
5
6
7
|
def print_list(head): cur = head while cur != None: print(cur.data,end=' ') cur = cur.next |
递归法 反转链表：
|
1
|
def reverse_list(head): |
三要素：
- 1.明确函数功能，该函数可以将链表反转，并返回一个头节点
- 2.结束条件：当链表为空或只有一个节点时返回
|
1
2
|
if head==None or head.next==None: return head |
-
3.等价条件（缩小范围），对于数组来讲，缩小范围是n——>n-1，对于链表来讲则可以考虑
head——
|
1
2
|
>head.next reverse = reverse_list(head.next) #假设reverse是head以后的、已经反转过的链表 |
接下来要做的是将head节点接到已经反转过的reverse上：
|
1
2
3
4
|
tmp = head.next tmp.next = head head.next = None return reverse #返回新的列表 |
迭代法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
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) |
正序打印：
|
1
2
3
4
|
print('原始list：') print_list(head) print('\n') |
反转后打印：
|
1
2
3
4
5
|
revere = reverse_list(head) print('反转一次的list：') print_list(revere) print('\n') |
反转2：
|
1
2
3
4
5
6
7
8
9
10
|
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链表反转内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/qq_34062683/article/details/121308565
