Easy

题目描述

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

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

  • 链表中节点数目在范围 [1, 10^5] 内
  • 0 <= Node.val <= 9

进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解题思路

解题思路

判断链表是否为回文有三种主要方法：

方法一：转换为数组（简单直观）

将链表节点值依次存入数组，然后使用双指针判断数组是否回文。时间复杂度 O(n)，空间复杂度 O(n)。

方法二：使用栈（递归思想）

遍历链表将所有值压入栈中，再次遍历链表时与栈顶元素比较。由于栈的后进先出特性，可以实现逆序比较。

方法三：快慢指针 + 反转链表（最优解）推荐

这是满足进阶要求的 O(1) 空间解法：

  1. 使用快慢指针找到链表中点
  2. 反转链表的后半部分
  3. 从头尾两端同时向中间遍历比较
  4. 恢复链表结构（可选）

快慢指针技巧：快指针每次走两步，慢指针每次走一步，当快指针到达末尾时，慢指针正好在中点位置。对于奇数长度链表，慢指针指向中间节点；对于偶数长度链表，慢指针指向前半部分的最后一个节点。

这种方法既保证了时间效率，又实现了常数空间复杂度，是最优雅的解决方案。

代码实现

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;
        
        // 找到中点
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 反转后半部分
        ListNode* secondHalf = reverseList(slow->next);
        
        // 比较前后两部分
        ListNode* p1 = head;
        ListNode* p2 = secondHalf;
        bool result = true;
        while (p2) {
            if (p1->val != p2->val) {
                result = false;
                break;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        
        // 恢复链表
        slow->next = reverseList(secondHalf);
        
        return result;
    }
    
private:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True
        
        # 找到中点
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        # 反转后半部分
        second_half = self.reverse_list(slow.next)
        
        # 比较前后两部分
        p1, p2 = head, second_half
        result = True
        while p2:
            if p1.val != p2.val:
                result = False
                break
            p1 = p1.next
            p2 = p2.next
        
        # 恢复链表
        slow.next = self.reverse_list(second_half)
        
        return result
    
    def reverse_list(self, head):
        prev = None
        curr = head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev

public class Solution {
    public bool IsPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        
        // 找到中点
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 反转后半部分
        ListNode secondHalf = ReverseList(slow.next);
        
        // 比较前后两部分
        ListNode p1 = head, p2 = secondHalf;
        bool result = true;
        while (p2 != null) {
            if (p1.val != p2.val) {
                result = false;
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        
        // 恢复链表
        slow.next = ReverseList(secondHalf);
        
        return result;
    }
    
    private ListNode ReverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

var isPalindrome = function(head) {
    if (!head || !head.next) return true;
    
    // 找到中点
    let slow = head, fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 反转后半部分
    let secondHalf = reverseList(slow.next);
    
    // 比较前后两部分
    let p1 = head, p2 = secondHalf;
    let result = true;
    while (p2) {
        if (p1.val !== p2.val) {
            result = false;
            break;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
    
    // 恢复链表
    slow.next = reverseList(secondHalf);
    
    return result;
};

function reverseList(head) {
    let prev = null, curr = head;
    while (curr) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型快慢指针+反转数组转换栈方法
时间复杂度O(n)O(n)O(n)
空间复杂度O(1)O(n)O(n)

说明：

  • 推荐使用快慢指针+反转链表的方法，满足进阶要求的 O(1) 空间复杂度
  • 所有方法的时间复杂度都是 O(n)，需要遍历整个链表
  • 快慢指针方法只使用常数个额外变量，空间效率最优

相关题目