第Python判斷回文鏈表的方法什么是回文數(shù)？

回文數(shù)簡(jiǎn)單的說(shuō)就是正著倒著讀都是一樣的，比如：12321,1221,1111等等，正著讀也是12321，倒著讀也是12321。

首先，接收用戶輸入數(shù)字列表轉(zhuǎn)換成鏈表

比如用戶輸入：12321，轉(zhuǎn)換為鏈表后，如下圖

首先接收用戶輸入數(shù)字列表，每個(gè)數(shù)字用空格分隔，使用split截?cái)嘧址褂胢ap，把每個(gè)元素映射成int類型，然后再轉(zhuǎn)成list，使用循環(huán)取出每項(xiàng)元素添加到鏈表中。

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

代碼如下：

#鏈表類

classListNode:

def__init__(self,x):

self.val=x

self.next=None

#字符串轉(zhuǎn)換為鏈表

deflist_node(s):

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

l=ListNode(0)#創(chuàng)建頭節(jié)點(diǎn)為0的鏈表

p=l

foriinrange(len(lt)):

p.next=ListNode(lt[i])

p=p.next

returnl.next

判斷是否是回文

找中間位置處使用快慢指針?lè)?，慢指針一次跳一格，快指針一次?格，所以快指針是慢指針的2倍，當(dāng)快指針為None時(shí)，說(shuō)明鏈表結(jié)束了，也就是代碼中的fast.next.next=None時(shí)，鏈表結(jié)束，此時(shí)慢指針剛好指著鏈表的中間位置，所以就得到3是中間位置，從3的下一個(gè)位置。再將中間位置的下一個(gè)節(jié)點(diǎn)開(kāi)始的鏈表，進(jìn)行倒敘，也就是21，倒敘后為12。

再與中間位置前面一段鏈表進(jìn)行比較是否相等，如果p==None時(shí)說(shuō)明鏈表為None，直接返回True，p==None，q也一定為None（具體看后面的倒敘方法）

whilepisnotNoneandqisnotNone:

ifp.valisnotq.val:

returnFalse

q,p=q.next,p.next

完整代碼：

#是否是回文

defpalindrome(l):

iflisNone:

returnTrue

slow=fast=l

#查找中間節(jié)點(diǎn)，一快一慢指針，快的是慢的2倍，當(dāng)快指針為None時(shí)，說(shuō)明已經(jīng)找到中間節(jié)點(diǎn)了

whilefast.nextisnotNoneandfast.next.nextisnotNone:

slow=slow.next#慢指針每次向后移一個(gè)位置

fast=fast.next.next#快指針每次向后移2個(gè)位置

h=slow.next

q=reverse(h)#逆至無(wú)頭節(jié)點(diǎn)鏈表

slow.next=None

p=l

whilepisnotNoneandqisnotNone:

ifp.valisnotq.val:

returnFalse

q,p=q.next,p.next

ifqisNone:

returnTrue

else:

returnFalse

倒敘鏈表（頭插法）：聲明一個(gè)頭節(jié)點(diǎn)，然后遍歷每個(gè)節(jié)點(diǎn)，再頭插到鏈表里面，總共是4步；

第1步：保存當(dāng)前頭節(jié)點(diǎn)所只向的節(jié)點(diǎn)

第2步：使當(dāng)前節(jié)點(diǎn)指向頭節(jié)點(diǎn)所指向的節(jié)點(diǎn)

第3步：使頭節(jié)點(diǎn)只向當(dāng)前節(jié)點(diǎn)

第4步：使指針（p）指向下一個(gè)節(jié)點(diǎn)，指向下一次循環(huán)

頭插法圖解：

完整代碼：

#逆置不帶頭結(jié)點(diǎn)的單鏈表

defreverse(head):

h=ListNode(0)

p=head

whilepisnotNone:

x=p.next#保存著當(dāng)前節(jié)點(diǎn)指向的下一個(gè)節(jié)點(diǎn)

p.next=h.next#當(dāng)前項(xiàng)的指向節(jié)點(diǎn)指向頭節(jié)點(diǎn)指向的節(jié)點(diǎn)

h.next=p#頭節(jié)點(diǎn)再指向當(dāng)前節(jié)點(diǎn)

p=x#使節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)

returnh.next

完整代碼

#回文鏈表，輸入1-2輸出false,輸入1-

#鏈表類

classListNode:

def__init__(self,x):

self.val=x

self.next=None

#字符串轉(zhuǎn)換為鏈表

deflist_node(s):

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

l=ListNode(0)#創(chuàng)建頭節(jié)點(diǎn)為0的鏈表

p=l

foriinrange(len(lt)):

p.next=ListNode(lt[i])

p=p.next

returnl.next

#逆置不帶頭結(jié)點(diǎn)的單鏈表

defreverse(head):

h=ListNode(0)

p=head

whilepisnotNone:

x=p.next#保存著當(dāng)前節(jié)點(diǎn)指向的下一個(gè)節(jié)點(diǎn)

p.next=h.next#當(dāng)前項(xiàng)的指向節(jié)點(diǎn)指向頭節(jié)點(diǎn)指向的節(jié)點(diǎn)

h.next=p#頭節(jié)點(diǎn)再指向當(dāng)前節(jié)點(diǎn)

p=x#使節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)

returnh.next

#是否是回文

defpalindrome(l):

iflisNone:

returnTrue

slow=fast=l

#查找中間節(jié)點(diǎn)，一快一慢指針，快的是慢的2倍，當(dāng)快指針為None時(shí)，說(shuō)明已經(jīng)找到中間節(jié)點(diǎn)了

whilefast.nextisnotNoneandfast.next.nextisnotNone:

slow=slow.next#慢指針每次向后移一個(gè)位置

fast=fast.next.next#快指針每次向后移2個(gè)位置

h=slow.next

q=reverse(h)#逆至無(wú)頭節(jié)點(diǎn)鏈表

slow.next=None

p=l

whilepisnotNoneandqisnotNone:

ifp.valisnotq.val:

returnFalse

q,p=q.next,p.next

ifqis