题目
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2 输出: false
示例 2:
输入: 1->2->2->1 输出: true
解题
方法一：转换为列表
把链表的值放入到列表中， 判断列表是否为回文列表
# 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: vals = [] cur = head while cur: vals.append(cur.val) cur = cur.next return vals==vals[::-1]
复杂度分析:
- 时间复杂度：O(n)O(n)，其中 nn 指的是链表的元素个数。
- 空间复杂度：O(n)O(n)，其中 nn 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。
方法二：双指针
将后半段链表反转，比如原来2→3→4→3→2变成2→3→4←3←2
然后一个指针从头开始，另一个指针从尾巴开始，到中间为止，遍历过程中假如值都相等，那么就是回文链表。
# 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 not head: return True fast=head.next slow=head # 找到前后半段分水岭 while fast and fast.next: fast=fast.next.next slow=slow.next #此时slow指向前一半的最后一个（偶数） 或者 中间结点（奇数） cur=slow.next # 将后半段就地逆置 pre=None while cur: tmp = cur.next cur.next = pre pre = cur cur = tmp # 开始比较 p=head q=pre while q: if q.val==p.val: q=q.next p=p.next else: return False return True
