双指针 7 （回文链表 leetcode 234）
2023-02-02 本文已影响0人
Sisyphus235
思想
双指针算法不仅应用于链表，在数组等数据结构中也有广泛应用。
核心思路是指向问题中的关键节点，根据问题的上下文逻辑变换位置，最终解决问题。
实例
回文链表 leetcode 234
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
输入：
head: ListNode，一个链表头结点；
输出：
bool，链表是否符合回文特征（从两端到中间经过的节点值相同）
举例：
当输入 head = [1,2,2,1] 时，从头尾到中间都是 [1,2]。
关键点
这里的关键点是从两头向中间走如何转换，因为链表是单向的，无法从尾端走向中间。
无论怎样转换，一定是要做翻转的。翻转的起始点是中间点，所以先用快慢两个指针的方式找到链表中点，fast 步长 2，slow 步长 1，当 fast 到达尾端时 slow 是中点。
然后从 slow 位置到尾端做一次翻转，接着从 head 和 slow 的位置分别遍历比较，如果有不同则不是回文。
如果想要取消翻转对原链表的影响，可以在此翻转后半部分链表。
（1）偶数 [1,2,2,1]
slow = fast = head = 1
slow = 2, fast = 2
slow = 2, fast = None
翻转变成 [1,2,1,2]
left = 1, right = 1（反转后的新头结点）
1=1, 2=2 符合回文
（2）奇数 [1,2,3]
slow = fast = head = 1
slow = 2, fast = 3 此时 fast.next = None 也应该停止。
翻转变成 [1,2,3]
left = 1, right = 3
1 != 3 不符合回文
编码
# -*- coding: utf8 -*-
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def palindrome_linked_list(head: Optional[ListNode]) -> bool:
# 处理边界条件
if head is None or head.next is None:
return True
rtn = True
# 获取链表中点
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
# 翻转后半部分链表
pre, cur = None, slow
while cur is not None:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
# 回文比较
left, right = head, pre
while right is not None:
if right.val != left.val:
rtn = False
break
left = left.next
right = right.next
# 恢复链表结构
after_pre, after_cur = None, pre
while after_cur is not None:
tmp = after_cur.next
after_cur.next = after_pre
after_pre = after_cur
after_cur = tmp
return rtn
