Palindrome Linked List
你会得到一个单向链表，它存储在两个长度相同的数组中。节点 i 保存值 values[i]，并链接到节点 next[i]。-1 表示链表结束，头节点是节点 0。节点并未按链表顺序存储，因此要沿着链接遍历。
如果从头节点到末尾读取的值，与从末尾到头节点读取的值相同，则返回 true；否则返回 false。
函数
- nextinteger-array
- 每个节点链接到的节点索引，最后一个节点为 -1
- valuesinteger-array
- 每个节点持有的值
- 返回值boolean
- 如果这个列表正着读和反着读都一样
约束条件
1 ≤ L ≤ 5000，其中L是next和values的长度。-100 ≤ values[i] ≤ 100- 每个
next[i]都是-1，或是从0到L-1的节点索引。 - 从节点
0开始，列表会恰好访问每个节点一次，然后到达-1。这里没有循环。
示例
- 输入
- next = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
- 输出
- true
- 解释
- 这些链接依次访问节点
0, 4, 1, 3, 2，因此列表内容为3, 1, 4, 1, 3。两个 3 相同，两个 1 相同，中间的4没有需要检查的对应项。
- 输入
- next = [2, -1, 3, 1]values = [4, 4, 9, 9]
- 输出
- true
- 解释
- 列表会依次访问节点
0, 2, 3, 1，并读取4, 9, 9, 4，两个方向都相同。
- 输入
- next = [2, -1, 1]values = [1, 2, 1]
- 输出
- false
- 解释
- 数组
values是[1, 2, 1]，但列表按0, 2, 1的顺序访问节点，并读取1, 1, 2。反过来是2, 1, 1，所以答案是false。
进阶
你能在 O(L) 时间内完成吗？额外内存为 O(1)。
提示
逐个打开提示，每个都会多透露一点。
回文检查会比较第一个值和最后一个值、第二个值和倒数第二个值，以此类推。在单向链表中，你只能向前遍历。怎样才能访问到链表末尾呢？
按列表顺序将值复制到数组中是可行的，但会占用
O(L)的内存。不复制的话，就必须从后往前遍历后半部分。更改链接可以实现这一点。用两个指针找到中间位置：
fast每次移动两条链接，slow每次移动一条。当fast无法继续移动时，slow就位于前半部分的末尾。反转slow后面的链接，然后同时从头节点和原来的最后一个节点开始遍历并比较。
题解
回文检查会将每个值与另一端镜像位置上的值配对。单向链表只能向前遍历，因此难点在于逆序读取后半部分。复制到数组中需要 O(L) 的内存，其中 L 是节点数；反转后半部分的链接则只需要 O(1)。
将这些值复制到数组中
思路
这里的指针是节点索引，向前移动的操作是 node = next[node]。遍历一次列表，并将每个值复制到一个数组中，这样你就可以从两端读取它们。比较第一个值和最后一个值，将两个索引都向中间移动；只要有任何值不匹配，就返回 false。如果长度是奇数，中间的值就是它自己的对应值。
必须读取每个值，因此 O(L) 时间复杂度是最优的。代价是额外使用 L 个整数。
算法
- 从节点
0遍历到-1，并将每个values[node]追加到数组中。 - 设置
i = 0，并将j设为最后一个索引。 - 当
i < j时，如果两个值不同，则返回false；否则，将i加 1，并将j减 1。 - 返回
true。
def isPalindrome(next, values):
# Write the values out in list order.
seq = []
node = 0
while node != -1:
seq.append(values[node])
node = next[node]
# Compare from both ends toward the middle.
i = 0
j = len(seq) - 1
while i < j:
if seq[i] != seq[j]:
return False
i += 1
j -= 1
return True将后半部分原地反转
思路
反转后半部分的链接，而不是复制它：从原来的最后一个节点开始遍历，就能向中间移动。为了找到中间节点，在 fast 前面还有两个链接时，fast 每移动两个链接，slow 就移动一个链接。slow 会停在前半部分的最后一个节点上；当 L 为奇数时，这就是中间节点。在第一个示例中，slow 的移动路径是 0 → 4 → 1，而 fast 的移动路径是 0 → 1 → 2，所以 slow 停在 4 上。
反转 slow 后面的节点，然后从头节点开始遍历 left，同时从反转后的半部分开始遍历 right：先比较 3 和 3，再比较 1 和 1。反转后的半部分不会比前半部分长，因此当 right 到头时停止，就能恰好比较需要比较的节点对。每个阶段最多遍历 L 个节点，并且只存储少量整数。在 R 中，修改 next_ 会复制整个向量一次，因此 R 使用 O(L) 内存。
算法
- 设置
slow = fast = 0。当next[fast]和next[next[fast]]都不等于-1时，让slow前进一个链接，fast前进两个链接。 - 反转从
next[slow]开始的列表：对于每个节点，保存它的链接，将它指向prev，然后让prev和该节点向前移动。 - 设置
left = 0，并将right = prev，也就是反转后半部分的头节点。 - 当
right != -1时，如果不匹配则返回false，否则让两个指针各前进一个链接。 - 返回
true。
def isPalindrome(next, values):
# Find the middle: fast moves two links for every one link slow moves.
slow = 0
fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
# slow is the last node of the first half (the middle node when the length is odd).
# Reverse the links of the second half.
prev = -1
node = next[slow]
while node != -1:
after = next[node]
next[node] = prev
prev = node
node = after
# prev is the old last node, now the head of the reversed half.
left = 0
right = prev
while right != -1:
if values[left] != values[right]:
return False
left = next[left]
right = next[right]
return True
易错点和边界情况
- 检查数组，而不是列表。在第三个示例中，
values是[1, 2, 1]，但列表显示的是1, 1, 2。 - 只检查
next[fast] != -1。这样fast接下来可能跳到-1并读取next[-1]，这在大多数语言中会导致越界，而在 Python 和 Ruby 中会静默地读取最后一项。 - 在
left结束时停止比较，而不是等到right结束。中间节点仍然指向旧的后半部分，因此从头节点开始遍历的路径更长。 - 反转列表时，保存
next[node]之前就覆盖它，这会丢失列表的其余部分。 - 在数组从 1 开始的 Lua 和 R 中，使用从 0 开始的节点 ID 读取
next[node]。应读取next[node + 1]。
常见问题3
回文链表检查的时间复杂度是多少？
对于包含 L 个节点的列表，每种方法的时间复杂度都是 O(L)，因为必须比较每个值。将这些值复制到数组或栈中会额外占用 O(L) 的内存；原地反转后半部分则只需 O(1) 的额外内存。
快慢指针如何找到链表的中间位置？
它们都从头部开始，快指针每走一步慢指针就走两步。快指针到达末尾时，它已经遍历了整个列表，而慢指针只遍历了一半。
反转列表的一半会破坏输入吗？
是的，它会改变后半部分的链接，而且在大多数语言中，这个数组属于调用方。如果还需要这个列表，就不要提前返回，先完成比较，然后再次反转后半部分。中间节点仍然指向后半部分的第一个节点，所以列表会恢复完整，额外内存为 O(1)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isPalindrome(next, values):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
next = [4, 3, -1, 2, 1] values = [3, 4, 3, 1, 1]
预期输出
true