题目
- 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
法一、复制+反转链表
- 把原链表翻转一下，与没翻转的链表对比，相同则是回文，返回True，不同则返回False。在进行链表翻转时需要把原链表节点一个一个取下来，用头插法放到新的链表中，导致原链表被拆毁，没法比较了，所以一开始先把原链表复制一份。
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:#空链表和单个节点链表
return True
# 复制链表
new_head = ListNode(0)#定义复制链表的头节点
new_current = new_head
current = head
while current:#当原链表没到链尾时进行复制
new_node = ListNode(current.val)#创建一个新的节点，把原链表当前指针所指的值赋与
new_current.next = new_node#把这个节点加载在新链表
new_current = new_current.next#新链表的当前指针后移
current = current.next#原链表的指针后移
# 反转链表
new_head2 = ListNode(0)#定义反转链表的头节点
pre = head#pre指针指向头
while pre:#当pre没到链表结尾时循环
cur = pre.next#把pre的下一个指针赋给指针cur
pre.next = new_head2.next#把新的头节点的next赋给pre的next
new_head2.next = pre#新的头节点的next指向pre
pre = cur#更新pre
# 比较链表是否回文
i, j = new_head.next, new_head2.next
while i and j:
if i.val != j.val:
return False
i = i.next
j = j.next
return True
- 时间复杂度为 O(n)，空间复杂度为 O(n)
法二、堆栈
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
stack = []#创建一个空栈 stack 用于存储链表节点
# step1: push
curr = head
while(curr):#遍历链表
stack.append(curr)#将节点依次压入栈中
curr = curr.next
# step2: pop and compare
node1 = head#链表的当前节点 node1
while(stack):
node2 = stack.pop()#弹出的栈顶元素
if node1.val != node2.val:
return False
node1 = node1.next
return True
- 时间复杂度为 O(n)，空间复杂度为 O(n)
法三、快慢指针和链表反转
1.使用快慢指针找到链表的中间节点。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针指向的节点即为链表的中间节点。
2.反转链表的后半部分。从中间节点开始，将后半部分链表进行反转操作。
3.比较链表的前半部分和反转后的后半部分。分别使用两个指针同时遍历两部分链表，比较节点的值是否相等。如果所有节点的值都相等，则链表是回文的；否则，链表不是回文的。
4.恢复链表并返回结果。将反转后的后半部分链表再次进行反转操作，使链表恢复原来的顺序。
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:#空链表和单个节点链表
return True
# 找到链表的中间节点
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 反转后半部分链表
prev = None
while slow:
next_node = slow.next
slow.next = prev
prev = slow
slow = next_node
# 比较链表的前半部分和反转后的后半部分
p1, p2 = head, prev
while p1 and p2:
if p1.val != p2.val:
return False
p1 = p1.next
p2 = p2.next
# 恢复链表
prev = None
while prev != None:
next_node = p2.next
p2.next = prev
prev = p2
p2 = next_node
return True
- 时间复杂度为 O(n)，空间复杂度为 O(1)