vvrf / DSA.log

问题拆解

判断单链表是不是回文。数组做法很简单：把值复制到列表里，用双指针从两端向中间比。但那是 O(n) 空间。

进阶要求 O(1) 空间。链表没法从尾往前走，所以关键是想办法让“后半段”能被正向遍历——把后半段原地反转，再和前半段逐一对照即可。

三步走：快慢指针找到中点，反转后半段，然后从两头同时向中间比较。整个过程只借用几个指针。

找中点 + 反转后半

public boolean isPalindrome(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    ListNode prev = null;
    while (slow != null) {
        ListNode nxt = slow.next;
        slow.next = prev;
        prev = slow;
        slow = nxt;
    }

    ListNode left = head, right = prev;
    while (right != null) {
        if (left.val != right.val) {
            return false;
        }
        left = left.next;
        right = right.next;
    }
    return true;
}

def isPalindrome(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev = slow
        slow = nxt

    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

func isPalindrome(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    var prev *ListNode
    for slow != nil {
        nxt := slow.Next
        slow.Next = prev
        prev = slow
        slow = nxt
    }

    left, right := head, prev
    for right != nil {
        if left.Val != right.Val {
            return false
        }
        left = left.Next
        right = right.Next
    }
    return true
}

// Box 链表反转后半段后，前半段的尾巴仍指向旧位置，双向对比会和借用检查冲突；
// 直接把值收集进 Vec 再双指针比较，同样是 O(n) 时间。
pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
    let mut vals = Vec::new();
    let mut cur = &head;
    while let Some(node) = cur {
        vals.push(node.val);
        cur = &node.next;
    }
    let (mut i, mut j) = (0, vals.len().saturating_sub(1));
    while i < j {
        if vals[i] != vals[j] {
            return false;
        }
        i += 1;
        j -= 1;
    }
    true
}

快指针一次两步、慢指针一次一步，快指针到头时慢指针正好落在后半段的起点（长度为奇数时落在正中，中间那个节点不影响比较）。接着用三指针把从 slow 开始的后半段反转，prev 成为反转后的新头，也就是原链表的尾节点。

比较时让 left 从头、right 从尾（反转后的头）同时往中间走。因为后半段更短或等长，以 right 走空作为结束条件即可，前半段多出来的中间节点不必比。

复杂度

指标	复杂度	原因
时间	`O(n)`	找中点、反转、比较各扫描一部分，合计线性
空间	`O(1)`	只用若干指针，原地反转后半段

可以迁移的模式

“从两端向中间比”在链表里做不到，就把后半段反转成可正向遍历；
快慢指针找中点是拆分链表的通用前置步骤；
需要 O(1) 空间时，优先考虑原地改指针，而不是复制数据。

这道题是链表基本操作的组合练习：中点、反转、比较三个小技能各来一次。