Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?
题意
判断链表是否是回文的
思路
- 栈
用一个栈存储链表所有结点的值，再对比出栈元素和正向遍历链表的值是否相等。
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
stack = []
tmp = head
while tmp:
stack.append(tmp.val)
tmp = tmp.next
while head:
cur = stack.pop()
if head.val != cur:
return False
head = head.next
return True
- 快慢指针
1.快慢指针找到链表的中点
2.翻转链表前半部分
3.回文校验
def isPalindrome2(self, head: ListNode) -> bool:
if head is None or head.next is None:
return True
slow = head
fast = head
new_head = None
while fast and fast.next:
slow = slow.next
fast = fast.next.next
while head != slow:
nxt = head.next
head.next = new_head
new_head = head
head = nxt
# 如果是奇数个结点，去掉后半部分第一个结点
if fast is not None:
slow = slow.next
while slow:
if slow.val != new_head.val:
return False
slow = slow.next
new_head = new_head.next
return True
