234 回文链表

一、题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

二、题解

思路： 找中点 + 反转后半 + 双指针比对，做到 O(1)O(1) 额外空间。

  • 用快慢指针找到链表中点（slow 停在前半部分末尾附近）。
  • 从中点开始原地反转后半部分链表，pre 指向反转后的新起点（即原链表尾节点）。
  • 让 head 从头、pre 从尾相向逐一比对节点值，全部相等则为回文。
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

 class Solution {
    public boolean isPalindrome(ListNode head) {
        // 【边界情况】节点为空或只有一个，天然是回文
        if (head == null || head.next == null) {
            return true;
        }

        ListNode slow = head, fast = head;
        boolean isPali = true;

        // 【步骤 1：快慢指针找中点】
        // 还是熟悉的配方：fast 跑两步，slow 跑一步。
        // 等 fast 跑到尽头时，slow 刚好走到链表的中点附近（也就是前半部分的尾巴）。
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 【步骤 2：反转后半部分链表】
        // 从中点 (slow) 开始，把后半截链表原地“掉头”。
        // 循环结束后，pre 指针会停在原链表的最后一个节点（即反转后的新起点）。
        ListNode cur = slow, pre = null;
        while(cur != null) {
            ListNode tmp = cur.next; // 暂存后面的节点
            cur.next = pre;          // 当前节点掉头指向上一个
            pre = cur;               // 步步推进
            cur = tmp;
        }

        // 【步骤 3：首尾齐进，逐个比对】
        // head 站在最开头，pre 站在最末尾。
        // 两者相向而行，一旦值不一样，就说明不是回文。
        while(head != null && pre != null) {
            if(head.val != pre.val) {
                isPali = false;
                // 注意：这里哪怕发现 false 也没有立刻 break，是为了保持代码结构，
                // 但实际工程中加上 break 会更高效。
            }
            head = head.next;
            pre = pre.next;
        }

        return isPali;
    }
}

时间复杂度：O(n)O(n)

空间复杂度：O(1)O(1)

评论