先把值存入链表,再使用双指针判断是否回文。
# 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
- 进阶解法:一次遍历找到链表后半段(快慢指针),翻转后半段(翻转链表),然后判断反转后的链表与原链表的值是否相等。
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