LeetCode 234 Palindrome Linked List

LeetCode

<div>

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

Example 1:

<pre>Input: head = [1,2,2,1] Output: true </pre>

Example 2:

<pre>Input: head = [1,2] Output: false </pre>

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?</div>

题目大意：

求一个LL是否回文

解题思路：

快慢指针 + Stack

解题步骤：

N/A

注意事项：

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

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)

算法II解题思路Recursion：

dfs(node)表示从这个点开始是否对称LL，这里利用后序遍历的方法，先走到头，在回溯时候通过一个global的left=left.next一个个比较

Python代码：

def isPalindrome(self, head: Optional[ListNode]) -> bool:
	left = head
	def dfs(node):
		nonlocal left
		if not node:
			return True
		if not dfs(node.next):
			return False
		if left.val != node.val:
			return False
		left = left.next
		return True
	return dfs(head)

算法III解题思路反转LL：

找到中点后反转后半，然后前半和后半的每个节点逐一比较。最后恢复后半的顺序