234. 回文链表

题目描述

Leetcode 地址

请判断一个链表是否为回文链表。

样例

Input: 1->2->2->1
Output: true

题解

栈实现

利用栈 FILO的性质，可以实现回文的检查。

找中点 + 翻转实现

• 切分中线，翻转对比，这里也有两种方式。

  

• 第二种方案中，需要判断奇偶

  如果在快慢指针中：

  • fast == null 前半部分是奇数个
  • fast.next == null 前半部分是偶数个

代码

找中点 + 翻转实现

这里我们选择第一种方式，即不用判断奇偶

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        def reverse(head):
            pre, cur = None, head 
            while cur:
                cur_next_bak = cur.next 
                cur.next = pre 

                pre = cur 
                cur = cur_next_bak
            return pre 
        
        if not head: return True 
        # 快慢指针实现中点的查找
        slow, fast = head, head.next 
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 切分中点
        mid = slow.next 
        # 后面的部分翻转
        mid = reverse(mid)

        while head and mid:
            if head.val != mid.val:
                return False
            head, mid = head.next, mid.next
        return True 

栈实现

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        stack = []
        p = head  # 第一次遍历是为了入栈
        while p:
            stack.append(p.val)
            p = p.next 
        p = head  # 第二次遍历是为了检测
        while p:  
            if p.val != stack.pop():
                return False 
            p = p.next 
        return True