没有白走的路，每一步都要算数🎈🎈🎈
文章目录
前言
反转链表是一个超级大众的题目了。
但是反转链表能够考察到的知识点却是很多的
比如如何使用递归，迭代来反转链表。对于初学者学习递归和迭代都是一个不错的练习。
还有这种题目的数据结构都不会明确，只能以注释的形式出现，很多人不能够调试，看到运行的结果，很让人头疼，所以本文除了带你了解到如何使用python来求解反转链表，还会把整个的pythonACM模式的代码给全部显示出来演示。
本文还有一个主要目的：巩固我学习python。希望我可以一直写下去吧，见证学习成长之路也是一件很开心的事情
一、反转链表题目
; 二、题目求解
1.迭代法求解
1.1 代码思路
给定一个链表如1->2->3->4->5
设计的算法的目的是把链表转成5->4->3->2->1,于是我们可以把链表先反转成这样1
1.2 代码图解
最初的链表
r = head.next
head.next = pre
pre = head
head = r
; 1.3 代码如下
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
pre = ListNode(4)
pre = None
r = ListNode(1)
while head != None:
r = head.next
head.next = pre
pre = head
head = r
return pre
2.递归法求解
1.1 代码思路
递归法，先把最后一个结点的前驱和后继元素改变了，再递归前面一个的前驱和后继。返回的是最后一个结点的位置。
1.2 代码图解
node = self.reverseList(head.next)
主要的作用是找到返回的第一个结点。
head.next.next = head
head.next = None
; 1.3 代码如下
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
if not head.next:
return head
node = self.reverseList(head.next)
head.next.next = head
head.next = None
return node
三、代码调试
1.题目中ListNode的结构类型
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
2.完整程序的代码
2.1 递归法求解
class ListNode(object):
def __init__(self,x):
self.val = x
self.next = None
class Solution(object):
def reverList(self,head):
if not head:
return None
if not head.next:
return head
node = self.reverList(head.next)
head.next.next = head
head.next = None
return node
if __name__ == '__main__':
head = ListNode(1)
cur = ListNode(2)
right = ListNode(3)
head.next = cur
cur.next = right
tmp = head
while tmp != None:
print(tmp.val)
tmp = tmp.next
print("要开始反转了")
tmp = Solution().reverList(head=head)
while tmp != None:
print(tmp.val)
tmp = tmp.next
print("反转结束了")
2.2 迭代法求解
class ListNode(object):
def __init__(self,x):
self.val = x
self.next = None
class Solution(object):
def reverList(self,head):
if head == None:
return None
pre = ListNode(1)
pre = None
r = ListNode(1)
while head != None:
r = head.next
head.next = pre
pre = head
head = r
return pre
if __name__ == '__main__':
head = ListNode(1)
cur = ListNode(2)
right = ListNode(3)
head.next = cur
cur.next = right
tmp = head
while tmp != None:
print(tmp.val)
tmp = tmp.next
print("要开始反转了")
tmp = Solution().reverList(head=head)
while tmp != None:
print(tmp.val)
tmp = tmp.next
print("反转结束了")
Original: https://blog.csdn.net/weixin_54201782/article/details/127588927
Author: Li&&Tao
Title: 反转链表的python题解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/669116/
转载文章受原作者版权保护。转载请注明原作者出处！