Python判断回文链表的方法是什么

Python判断回文链表的方法是什么

小编今天带大家了解Python判断回文链表的方法是什么，文中知识点介绍的非常详细。觉得有帮助的朋友可以跟着小编一起浏览文章的内容，希望能够帮助更多想解决这个问题的朋友找到问题的答案，下面跟着小编一起深入学习“Python判断回文链表的方法是什么”的知识吧。

什么是回文数？

回文数简单的说就是正着倒着读都是一样的，比如：12321,1221,1111等等，正着读也是12321，倒着读也是12321。

首先，接收用户输入数字列表转换成链表

比如用户输入：1 2 3 2 1，转换为链表后，如下图

首先接收用户输入数字列表，每个数字用空格分隔，使用split截断字符串，使用map，把每个元素映射成int类型，然后再转成list，使用循环取出每项元素添加到链表中。

lt=list(map(int,s.split('')))

代码如下：

#链表类classListNode:def__init__(self,x):self.val=xself.next=None#字符串转换为链表deflist_node(s):lt=list(map(int,s.split('')))l=ListNode(0)#创建头节点为0的链表p=lforiinrange(len(lt)):p.next=ListNode(lt[i])p=p.nextreturnl.next

判断是否是回文

找中间位置处使用快慢指针法，慢指针一次跳一格，快指针一次跳2格，所以快指针是慢指针的2倍，当快指针为None时，说明链表结束了，也就是代码中的fast.next.next=None时，链表结束，此时慢指针刚好指着链表的中间位置，所以就得到3是中间位置，从3的下一个位置。再将中间位置的下一个节点开始的链表，进行倒叙，也就是21，倒叙后为12。

再与中间位置前面一段链表进行比较是否相等，如果p==None时说明链表为None，直接返回True，p==None，q也一定为None（具体看后面的倒叙方法）

whilepisnotNoneandqisnotNone:ifp.valisnotq.val:returnFalseq,p=q.next,p.next

完整代码：

#是否是回文defpalindrome(l):iflisNone:returnTrueslow=fast=l#查找中间节点，一快一慢指针，快的是慢的2倍，当快指针为None时，说明已经找到中间节点了whilefast.nextisnotNoneandfast.next.nextisnotNone:slow=slow.next#慢指针每次向后移一个位置fast=fast.next.next#快指针每次向后移2个位置h=slow.nextq=reverse(h)#逆至无头节点链表slow.next=Nonep=lwhilepisnotNoneandqisnotNone:ifp.valisnotq.val:returnFalseq,p=q.next,p.nextifqisNone:returnTrueelse:returnFalse

倒叙链表（头插法）：声明一个头节点，然后遍历每个节点，再头插到链表里面，总共是4步；

第1步：保存当前头节点所只向的节点

第2步：使当前节点指向头节点所指向的节点

第3步：使头节点只向当前节点

第4步：使指针（p）指向下一个节点，指向下一次循环

头插法图解：

完整代码：

#逆置不带头结点的单链表defreverse(head):h=ListNode(0)p=headwhilepisnotNone:x=p.next#保存着当前节点指向的下一个节点p.next=h.next#当前项的指向节点指向头节点指向的节点h.next=p#头节点再指向当前节点p=x#使节点指向下一个节点returnh.next

完整代码

#回文链表，输入1->2输出false,输入1->#链表类classListNode:def__init__(self,x):self.val=xself.next=None#字符串转换为链表deflist_node(s):lt=list(map(int,s.split('')))l=ListNode(0)#创建头节点为0的链表p=lforiinrange(len(lt)):p.next=ListNode(lt[i])p=p.nextreturnl.next#逆置不带头结点的单链表defreverse(head):h=ListNode(0)p=headwhilepisnotNone:x=p.next#保存着当前节点指向的下一个节点p.next=h.next#当前项的指向节点指向头节点指向的节点h.next=p#头节点再指向当前节点p=x#使节点指向下一个节点returnh.next#是否是回文defpalindrome(l):iflisNone:returnTrueslow=fast=l#查找中间节点，一快一慢指针，快的是慢的2倍，当快指针为None时，说明已经找到中间节点了whilefast.nextisnotNoneandfast.next.nextisnotNone:slow=slow.next#慢指针每次向后移一个位置fast=fast.next.next#快指针每次向后移2个位置h=slow.nextq=reverse(h)#逆至无头节点链表slow.next=Nonep=lwhilepisnotNoneandqisnotNone:ifp.valisnotq.val:returnFalseq,p=q.next,p.nextifqisNone:returnTrueelse:returnFalseif__name__=='__main__':print("回文链表")l=list_node(input())print(palindrome(l))

运行结果图：

python主要应用领域有哪些

1、云计算，典型应用OpenStack。2、WEB前端开发，众多大型网站均为Python开发。3.人工智能应用，基于大数据分析和深度学习而发展出来的人工智能本质上已经无法离开python。4、系统运维工程项目，自动化运维的标配就是python+Django/flask。5、金融理财分析，量化交易，金融分析。6、大数据分析。

感谢大家的阅读，以上就是“Python判断回文链表的方法是什么”的全部内容了，学会的朋友赶紧操作起来吧。相信恰卡编程网小编一定会给大家带来更优质的文章。谢谢大家对恰卡编程网网站的支持！