Python判斷回文鏈表的方法

更新時(shí)間：2022年01月17日 14:44:46 作者：小星博博

這篇文章主要介紹了Python判斷回文鏈表,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

什么是回文數(shù)？

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

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

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

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

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

代碼如下：

# 鏈表類
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
# 字符串轉(zhuǎn)換為鏈表
def list_node(s):
    lt = list(map(int, s.split(' ')))
    l = ListNode(0)  # 創(chuàng)建頭節(jié)點(diǎn)為0的鏈表
    p = l
    for i in range(len(lt)):
        p.next = ListNode(lt[i])
        p = p.next
    return l.next

判斷是否是回文

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

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

while p is not None and q is not None:
        if p.val is not q.val:
            return False
        q, p = q.next, p.next

完整代碼：

# 是否是回文
def palindrome(l):
    if l is None:
        return True
    slow = fast = l
    # 查找中間節(jié)點(diǎn)，一快一慢指針，快的是慢的2倍，當(dāng)快指針為None時(shí)，說(shuō)明已經(jīng)找到中間節(jié)點(diǎn)了
    while fast.next is not None and fast.next.next is not None:
        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
    while p is not None and q is not None:
        if p.val is not q.val:
            return False
        q, p = q.next, p.next
    if q is None:
        return True
    else:
        return False

倒敘鏈表（頭插法）：聲明一個(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)的單鏈表
def reverse(head):
    h = ListNode(0)
    p = head
    while p is not None:
        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)
    return h.next

完整代碼

# 回文鏈表，輸入1->2輸出false,輸入1->
# 鏈表類
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
# 字符串轉(zhuǎn)換為鏈表
def list_node(s):
    lt = list(map(int, s.split(' ')))
    l = ListNode(0)  # 創(chuàng)建頭節(jié)點(diǎn)為0的鏈表
    p = l
    for i in range(len(lt)):
        p.next = ListNode(lt[i])
        p = p.next
    return l.next

# 逆置不帶頭結(jié)點(diǎn)的單鏈表
def reverse(head):
    h = ListNode(0)
    p = head
    while p is not None:
        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)
    return h.next

# 是否是回文
def palindrome(l):
    if l is None:
        return True
    slow = fast = l
    # 查找中間節(jié)點(diǎn)，一快一慢指針，快的是慢的2倍，當(dāng)快指針為None時(shí)，說(shuō)明已經(jīng)找到中間節(jié)點(diǎn)了
    while fast.next is not None and fast.next.next is not None:
        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
    while p is not None and q is not None:
        if p.val is not q.val:
            return False
        q, p = q.next, p.next
    if q is None:
        return True
    else:
        return False

if __name__ == '__main__':
    print("回文鏈表")
    l = list_node(input())
    print(palindrome(l))

運(yùn)行結(jié)果圖：