【忍者算法】从生活场景到回文链表：探索对称性检测｜LeetCode 234 回文链表

技术分享 12个月前 (02-15) 0 999+

关注

从生活场景到回文链表：探索对称性检测

生活中的回文现象

在日常生活中，回文无处不在。比如"上海自来水来自海上"、"12321"这样正着读和倒着读都一样的字符串或数字，就是回文。把这个概念扩展到链表，我们就得到了今天要讨论的回文链表问题：一个链表从前往后读和从后往前读的结果是否相同。

问题描述

LeetCode第234题"回文链表"要求：给你一个单链表的头节点 head，请判断该链表是否为回文链表。

例如：

输入：1 → 2 → 2 → 1 输出：true  输入：1 → 2 → 3 → 2 → 1 输出：true  输入：1 → 2 → 3 → 3 → 1 输出：false

基础知识准备

这道题的核心是利用我们之前学过的"反转链表"。如果不熟悉链表反转，建议先复习上一篇文章。记住，链表反转是一块基石，在这里我们要用它来解决更复杂的问题。

直观解法：转换为数组

最简单的想法是：把链表转换成数组，然后用双指针从两端向中间移动比较。这就像把一摞扑克牌摊开在桌上，从两端开始对比每张牌是否相同。

数组法实现

public boolean isPalindrome(ListNode head) {     List<Integer> vals = new ArrayList<>();          // 将链表值复制到数组中     ListNode current = head;     while (current != null) {         vals.add(current.val);         current = current.next;     }          // 使用双指针判断是否回文     int left = 0, right = vals.size() - 1;     while (left < right) {         if (!vals.get(left).equals(vals.get(right))) {             return false;         }         left++;         right--;     }          return true; }

优化解法：反转后半部分

仔细思考，我们其实不需要额外的数组。可以用这个巧妙的方法：

找到链表中点
反转后半部分
比较前后两半是否相同
（可选）恢复链表原状

这就像把一叠纸牌分成两半，把后半部分倒过来，然后一张张对比。

寻找中点：快慢指针法

想象两个人在跑道上跑步，一个速度是另一个的两倍。当快跑者跑到终点时，慢跑者正好在中点！

详细代码实现

public boolean isPalindrome(ListNode head) {     if (head == null || head.next == null) {         return true;     }          // 第1步：找到中点     ListNode slow = head;     ListNode fast = head;     while (fast.next != null && fast.next.next != null) {         slow = slow.next;         fast = fast.next.next;     }          // 第2步：反转后半部分     ListNode secondHalf = reverseList(slow.next);          // 第3步：比较两半是否相同     ListNode firstHalf = head;     ListNode temp = secondHalf; // 保存开始位置，用于之后恢复     boolean result = true;     while (secondHalf != null) {         if (firstHalf.val != secondHalf.val) {             result = false;             break;         }         firstHalf = firstHalf.next;         secondHalf = secondHalf.next;     }          // 第4步：恢复链表（可选）     slow.next = reverseList(temp);          return result; }  // 链表反转函数（使用我们之前学过的方法） private ListNode reverseList(ListNode head) {     ListNode prev = null;     ListNode curr = head;     while (curr != null) {         ListNode nextTemp = curr.next;         curr.next = prev;         prev = curr;         curr = nextTemp;     }     return prev; }

图解过程

以1→2→3→2→1为例：

1) 初始状态： 1 → 2 → 3 → 2 → 1  2) 找到中点： 1 → 2 → [3] → 2 → 1 slow指向3  3) 反转后半部分： 1 → 2 → 3 ← 2 ← 1  4) 比较两半： (1 → 2) 和 (1 → 2) 比较  5) 恢复原状： 1 → 2 → 3 → 2 → 1