image.png

先把值存入鏈表，再使用雙指針判斷是否回文。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        val = []
        while head:
            val.append(head.val)
            head=head.next
        lp = 0
        rp = len(val)-1
        while lp<rp: 
            if not val[lp]==val[rp]:
                return False
            lp+=1
            rp-=1
        return True

image.png

• 進(jìn)階解法：一次遍歷找到鏈表后半段（快慢指針），翻轉(zhuǎn)后半段（翻轉(zhuǎn)鏈表），然后判斷反轉(zhuǎn)后的鏈表與原鏈表的值是否相等。

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        # 反轉(zhuǎn)后半段的鏈表，再比較
        # 快慢指針一趟可以找到中點(diǎn)
        if not head:
            return True
        def find_sec_head(head):
            sp=head
            fp=head
            while fp and fp.next:
                sp=sp.next
                fp=fp.next.next
            return sp

        def reverse(head):
            pre=None
            cur=head
            nxt = head.next
            while cur:
                nxt=cur.next
                cur.next=pre
                pre=cur
                cur=nxt
            return pre

        sec_head = find_sec_head(head)
        reverse_head = reverse(sec_head)
        
        while reverse_head:
            if head.val!=reverse_head.val:
                return False
            head=head.next
            reverse_head=reverse_head.next
        return True

image.png