江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode第234题：回文链表

LeetCode第234题：回文链表

问题描述

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

难度：简单

示例

示例 1：

输入：1->2
输出：false

示例 2：

输入：1->2->2->1
输出：true

进阶

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

解题思路

回文是指正着读和倒着读都一样的序列，如 “level” 或 “racecar”。判断一个链表是否为回文链表，需要从两端向中间比较元素是否相同。然而，单链表只能从头到尾遍历，无法直接从尾部开始访问。

方法一：使用栈

一个直观的思路是使用栈来存储链表的前半部分，然后与后半部分进行比较：

  1. 遍历整个链表，将所有节点的值存入栈中
  2. 再次遍历链表，每遍历一个节点，就从栈中弹出一个元素进行比较
  3. 如果所有对比都相同，则为回文链表

这种方法时间复杂度为 O(n)，空间复杂度为 O(n)。

方法二：使用快慢指针找中点 + 反转后半部分链表

为了达到 O(1) 的空间复杂度，我们可以：

  1. 使用快慢指针找到链表的中点
  2. 反转链表的后半部分
  3. 比较前半部分和反转后的后半部分
  4. （可选）恢复链表原来的结构（再次反转后半部分）

这种方法时间复杂度为 O(n)，空间复杂度为 O(1)。

方法三：递归

我们还可以用递归来解决这个问题。递归的特点是先走到链表末尾，然后回溯比较：

  1. 用一个全局指针指向链表头部
  2. 递归到链表尾部
  3. 回溯过程中，将全局指针指向的节点值与当前递归节点的值比较
  4. 全局指针不断向前移动，进行下一次比较

这种方法时间复杂度为 O(n)，空间复杂度为 O(n)（因为递归使用了系统栈空间）。

代码实现

方法一：使用栈

C#实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public bool IsPalindrome(ListNode head) {
        Stack<int> stack = new Stack<int>();
        ListNode current = head;
        
        // 将所有节点的值存入栈中
        while (current != null) {
            stack.Push(current.val);
            current = current.next;
        }
        
        // 再次遍历链表，比较每个节点与栈顶元素
        current = head;
        while (current != null) {
            if (current.val != stack.Pop()) {
                return false;
            }
            current = current.next;
        }
        
        return true;
    }
}

Python实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        stack = []
        current = head
        
        # 将所有节点的值存入栈中
        while current:
            stack.append(current.val)
            current = current.next
        
        # 再次遍历链表，比较每个节点与栈顶元素
        current = head
        while current:
            if current.val != stack.pop():
                return False
            current = current.next
        
        return True

C++实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> s;
        ListNode* current = head;
        
        // 将所有节点的值存入栈中
        while (current) {
            s.push(current->val);
            current = current->next;
        }
        
        // 再次遍历链表，比较每个节点与栈顶元素
        current = head;
        while (current) {
            if (current->val != s.top()) {
                return false;
            }
            s.pop();
            current = current->next;
        }
        
        return true;
    }
};

方法二：快慢指针 + 反转链表

C#实现

public class Solution {
    public bool IsPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        
        // 1. 使用快慢指针找到链表中点
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 如果链表长度为奇数，slow需要前进一步
        if (fast != null) {
            slow = slow.next;
        }
        
        // 2. 反转后半部分链表
        ListNode secondHalfReversed = ReverseList(slow);
        ListNode firstHalf = head;
        
        // 3. 比较前半部分和反转后的后半部分
        while (secondHalfReversed != null) {
            if (firstHalf.val != secondHalfReversed.val) {
                return false;
            }
            firstHalf = firstHalf.next;
            secondHalfReversed = secondHalfReversed.next;
        }
        
        return true;
    }
    
    private ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        
        return prev;
    }
}

Python实现

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:
            return True
        
        # 1. 使用快慢指针找到链表中点
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # 如果链表长度为奇数，slow需要前进一步
        if fast:
            slow = slow.next
        
        # 2. 反转后半部分链表
        second_half_reversed = self.reverseList(slow)
        first_half = head
        
        # 3. 比较前半部分和反转后的后半部分
        while second_half_reversed:
            if first_half.val != second_half_reversed.val:
                return False
            first_half = first_half.next
            second_half_reversed = second_half_reversed.next
        
        return True
    
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        current = head
        
        while current:
            next_temp = current.next
            current.next = prev
            prev = current
            current = next_temp
        
        return prev

C++实现

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) {
            return true;
        }
        
        // 1. 使用快慢指针找到链表中点
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 如果链表长度为奇数，slow需要前进一步
        if (fast) {
            slow = slow->next;
        }
        
        // 2. 反转后半部分链表
        ListNode* secondHalfReversed = reverseList(slow);
        ListNode* firstHalf = head;
        
        // 3. 比较前半部分和反转后的后半部分
        while (secondHalfReversed) {
            if (firstHalf->val != secondHalfReversed->val) {
                return false;
            }
            firstHalf = firstHalf->next;
            secondHalfReversed = secondHalfReversed->next;
        }
        
        return true;
    }
    
private:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* current = head;
        
        while (current) {
            ListNode* nextTemp = current->next;
            current->next = prev;
            prev = current;
            current = nextTemp;
        }
        
        return prev;
    }
};

性能分析

时间复杂度

  • 方法一（使用栈）：O(n)，需要两次遍历链表。
  • 方法二（快慢指针 + 反转链表）：O(n)，需要遍历链表找中点O(n/2)，反转后半部分O(n/2)，比较两部分O(n/2)。
  • 方法三（递归）：O(n)，递归需要遍历整个链表。

空间复杂度

  • 方法一（使用栈）：O(n)，需要额外空间存储链表中所有元素。
  • 方法二（快慢指针 + 反转链表）：O(1)，只需要几个指针变量。
  • 方法三（递归）：O(n)，递归调用栈的空间。

不同方法的性能对比

方法 时间复杂度 空间复杂度 优势 劣势
使用栈 O(n) O(n) 实现简单，不修改原链表 空间复杂度较高
快慢指针 + 反转链表 O(n) O(1) 空间复杂度低 实现复杂，修改了原链表结构（可以恢复）
递归 O(n) O(n) 代码优雅 空间复杂度高，可能栈溢出

各语言实现的性能比较

语言 方法一执行时间 方法二执行时间
C++ ~12ms ~8ms
C# ~100ms ~80ms
Python ~60ms ~50ms

C++实现通常效率最高，因为其直接操作内存，没有垃圾回收开销。Python和C#的效率较低，但更易于实现和维护。

代码特点

  1. 所有方法都利用了回文的对称特性
  2. 在方法二中，正确处理了链表长度为奇数和偶数的情况
  3. 快慢指针技巧在寻找链表中点时非常有用
  4. 链表反转是一个常见的基本操作，在多种问题中都有应用

优化方向

  1. 在方法二中，可以选择是否恢复链表原来的结构。如果需要保持原链表不变，可以在比较完成后再次反转后半部分。
  2. 在实际应用中，可以根据内存限制选择合适的方法：
    • 如果内存充足，可以选择方法一，实现简单且不修改原链表
    • 如果内存受限，可以选择方法二，空间复杂度为O(1)

常见错误

  1. 在找链表中点时，没有正确处理链表长度为奇数和偶数的情况
  2. 反转链表时的指针操作错误，导致链表断裂或循环引用
  3. 在比较阶段，没有处理好前半部分和后半部分长度不同的情况（奇数长度链表）

相关题目

  • LeetCode 206: 反转链表
  • LeetCode 876: 链表的中间结点
  • LeetCode 9: 回文数
  • LeetCode 125: 验证回文串
  • LeetCode 5: 最长回文子串