回文链表

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

• 进阶解法：一次遍历找到链表后半段（快慢指针），翻转后半段（翻转链表），然后判断反转后的链表与原链表的值是否相等。

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        # 反转后半段的链表，再比较
        # 快慢指针一趟可以找到中点
        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