LeetCode 234 Palindrome Linked List

LeetCode

Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

The number of nodes in the list is in the range [1, 10<sup>5</sup>]. 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

题目大意：

求一个LL是否回文

解题思路：

快慢指针 + Stack

解题步骤：

N/A

注意事项：

1. 快慢指针找到中点，找的同时，慢指针所有节点入栈。慢指针继续走，比较stack节点和慢指针节点。
2. 不涉及删除，所以不需要哟用到fake_node
3. 中位数可能有1-2个。奇偶问题，若fast指向节点(另一情况是None), 表明是奇数个，slow在第二个循环前多走一步，跳过最中间的节点

Python代码：

def isPalindrome(self, head: ListNode) -> bool:
	fast, slow = head, head
	stack = []
	while fast and fast.next:
		stack.append(slow)
		slow = slow.next
		fast = fast.next.next
	if fast:
		slow = slow.next
	while slow:
		if stack.pop().val != slow.val:
			return False
		slow = slow.next
	return True

算法分析：

时间复杂度为O(n)，空间复杂度O(n)