时间：2020-07-04
题目地址：https://leetcode-cn.com/problems/palindrome-linked-list
题目难度：Easy
题目描述：
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2 输出: false 示例 2:
输入: 1->2->2->1 输出: true 进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路1：快慢指针，一半堆栈
代码段1：通过
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def isPalindrome(self, head: ListNode) -> bool: if head == None or head.next == None: return True if head.next.next == None: if head.val == head.next.val: return True else: return False slow, fast, temp = head, head, [head.val] while fast.next != None and fast.next.next != None: fast = fast.next.next slow = slow.next temp.append(slow.val) if fast.next == None: temp.pop() print(temp) while slow.next != None: slow = slow.next if slow.val == temp[-1]: temp.pop() else: return False if len(temp) == 0: return True else: return False总结：
我写的太烂了，是得背代码了么看下优化的 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def isPalindrome(self, head: ListNode) -> bool: stack = [] slow = head fast = head # step1: push while(fast and fast.next): stack.append(slow) slow = slow.next fast = fast.next.next if fast: # 奇数 slow = slow.next # step2: pop and compare while(stack): curr = stack.pop() if curr.val != slow.val: return False slow = slow.next return True思路2：快慢指针，反转
代码段2：通过
class Solution: def isPalindrome(self, head: ListNode) -> bool: slow,fast,prev = head,head,None while fast is not None: slow = slow.next fast = fast.next.next if fast.next is not None else fast.next while slow is not None: slow.next, slow, prev= prev, slow.next, slow while head and prev: if head.val != prev.val: return False head = head.next prev = prev.next return True总结：
牛，这道题也算简单，我累了= =思路3：反转原始链表存入一条新的链表【2021-2-17】
代码段3：一个超时
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next import copy class Solution: def isPalindrome(self, head: ListNode) -> bool: old = copy.deepcopy(head) # 链表的深复制，用于与反转后的链表比较 print(old) temp = head def reverse(head): if head == None or head.next == None: return head new_head = reverse(head.next) head.next.next = head head.next = None return new_head new = reverse(temp) print(new) while new and old: if new.val != old.val: return False new = new.next old = old.next return True总结：
对象赋值传递的是对象的引用，copy.copy() 浅拷贝，不会克隆子对象，copy.deepcopy()深拷贝，会克隆子对象思路4：利用递归函数本身的堆栈实现倒序
代码段4：通过
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: left = ListNode() def isPalindrome(self, head: ListNode) -> bool: global left left = head def traverse(right): if right == None: return True res = traverse(right.next) //链表的后序遍历（倒序遍历链表） global left res = right.val == left.val and res left = left.next return res return traverse(head)总结：
链表的前序遍历和后序遍历与二叉树一致，可实现顺序遍历 倒序遍历链表思路5：利用快慢指针，回文的特殊性
代码段5：通过
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def isPalindrome(self, head: ListNode) -> bool: slow, fast = head, head while fast != None and fast.next != None: slow = slow.next fast = fast.next.next # 快慢指针,找到链表中点 if fast != None: slow = slow.next # 长度为奇数，slow再往后一步 def traverse(slow): # 反转链表 pre, cur = None, slow while cur: nxt = cur.next cur.next = pre pre = cur cur = nxt return pre left = head right = traverse(slow) # 从slow开始反转，进行比较 while right: if left.val != right.val: return False left = left.next right = right.next return True总结：
这道题作为简单简直毫无天理