解题思路
回文链表有一个标志的特性就是以首尾相应的形式往中间靠拢的。比如1->2->3->3->2->1
,1对应末尾的1, 2对应倒数第二的2以此类推。
所以我们可以借助双指针来完美解决这个问题。一个指针指向头,一个指针指向末尾同步往中间靠拢,如果全程都是相等的那就是回文链表否则就不是。
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not (head and head.next): return True
temp = []
while head:
temp.append(head.val)
head = head.next
i,j = 0, len(temp)-1
while i < j:
if temp[i] != temp[j]: return False
i += 1
j -= 1
return True