请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
解题思路
- 找到链表的中间节点
- 反转链表
- 遍历这两个链表,如果遍历过程中发现两个链表节点不同,说明不是回文链表,直接返回False;如果链表遍历完了,说明是回文链表,返回True
# 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
p = ListNode(-1)
p.next,low,fast = head, p,p
while fast and fast.next:
low,fast = low.next,fast.next.next
cur,pre = low.next,None
low.next = None
while cur:
cur.next,pre,cur = pre, cur, cur.next
a,b = p.next,pre
while b:
if b.val != a.val:
return False
a,b = a.next, b.next
return True
网友评论