【算法刷题】总结规律 算法题目第2讲 [234] 回文链表，因为深浅拷贝引出的bug

配合b站视频讲解食用更佳:https://www.bilibili.com/video/BV1vW4y1P7V7
核心提示：好几道题是处理有序数组的！

适合人群：考研/复试/面试
解决痛点：1. 刷了就忘 2.换一道相似的题就不会
学完后会输出：对每类题目的框架

#
# @lc app=leetcode.cn id=234 lang=python3
#
# [234] 回文链表
#
from typing import Optional
import copy
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next
# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reserve(self,head:Optional[ListNode])->Optional[ListNode]:if (not head) or (not head.next):return headlast = self.reserve(head.next)head.next.next = headhead.next = Nonereturn lastdef isPalindrome(self, head: Optional[ListNode]) -> bool:head1 = copy.deepcopy(head)res = self.reserve(head1)while head and res:if head.val == res.val:head = head.nextres = res.nextelse:return Falsereturn True# @lc code=end
# 1,1,2,1
n0 = ListNode(1)
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(1)
n0.next = n1
n1.next = n2
n2.next = n3
Solution().isPalindrome(n0)

判断链表是否是回文链表的问题，对应力扣234题：题目连接https://leetcode.cn/problems/palindrome-linked-list/description/
这道题我采用的思路是，翻转链表，然后和原链表挨个节点做比较。
但是写出了bug，
bug 在这里，是深浅拷贝的问题
res = self.reserve(head) 是不行的，因为head会被reserve改写，然后浅拷贝也是不行的，会报错。深拷贝是对的。

 head1 = copy.deepcopy(head)res = self.reserve(head1)

对于简单的 object，例如不可变对象（数值，字符串，元组），用 shallow copy 和 deep copy 没区别

复杂的 object， 如 list 中套着 list 的情况，shallow copy 中的 子list，并未从原 object 真的「独立」出来。也就是说，如果你改变原 object 的子 list 中的一个元素，你的 copy 就会跟着一起变。这跟我们直觉上对「复制」的理解不同。

一个很考察基本功，但是很赞的解法：
step1. 找中点
step2. 翻转中点后面的链表
step3. 比较left 和 right

    def isPalindrome(self, head: Optional[ListNode]) -> bool:if not (head and head.next):return True# 找中点slow,fast = head,headwhile fast and fast.next:fast = fast.next.nextslow = slow.nextif fast:slow = slow.nextleft,right= head,self.reserve(slow)while left and right:if left.val != right.val:return Falseleft = left.nextright = right.nextreturn True