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
方法：先把linked list分成两半之后，reverse the second half。然后比较两半的node的值。
time complexity：O(n) space complexity：O(1)
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def isPalindrome(self, head: ListNode) -> bool: if not head or not head.next: return True slow = head fast = head while fast and fast.next and fast.next.next: slow = slow.next fast = fast.next.next p = slow.next slow.next = None newHead = None while p: _next = p.next p.next = newHead newHead = p p = _next p1 = head p2 = newHead while p1 and p2: if p1.val != p2.val: return False p1 = p1.next p2 = p2.next if not p1 and not p2: return True if not p1 and p2 and not p2.next: return True if not p2 and p1 and not p1.next: return True return False
LeetCode 234 - Palindrome Linked List (Easy)
原文：https://www.cnblogs.com/sky37/p/13946934.html