题解 | 链表的回文结构

解题思路

这是一个判断链表是否为回文结构的问题。为了满足 $\mathcal{O}(1)$ 的空间复杂度，我们可以：

找到链表中点
反转后半部分
比较前后两部分
恢复链表结构（可选）

关键点：

使用快慢指针找中点
原地反转后半部分链表
比较两部分是否相同
不使用额外空间

算法步骤：

使用快慢指针找到中点
反转后半部分链表
从头和中点开始比较
可选：恢复链表原始结构

代码

cpp
java
python

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        if (!A || !A->next) {
            return true;
        }
        
        // 找到中点
        ListNode* slow = A;
        ListNode* fast = A;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 反转后半部分
        ListNode* secondHalf = reverseList(slow->next);
        
        // 比较两部分
        ListNode* firstHalf = A;
        ListNode* temp = secondHalf;  // 保存起点以便恢复
        bool result = true;
        
        while (secondHalf) {
            if (firstHalf->val != secondHalf->val) {
                result = false;
                break;
            }
            firstHalf = firstHalf->next;
            secondHalf = secondHalf->next;
        }
        
        // 恢复链表结构（可选）
        slow->next = reverseList(temp);
        
        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;
    }
};

import java.util.*;

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if (A == null || A.next == null) {
            return true;
        }
        
        // 找到中点
        ListNode slow = A;
        ListNode fast = A;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 反转后半部分
        ListNode secondHalf = reverseList(slow.next);
        
        // 比较两部分
        ListNode firstHalf = A;
        ListNode temp = secondHalf; // 保存起点以便恢复
        boolean result = true;
        
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                result = false;
                break;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }
        
        // 恢复链表结构（可选）
        slow.next = reverseList(temp);
        
        return result;
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

#!/usr/bin/env python
# -*- coding: utf-8 -*-

class PalindromeList:
    def chkPalindrome(self, A):
        # 处理空链表和单节点链表
        if not A or not A.next:
            return True
            
        # 找到中点
        slow = fast = A
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
            
        # 反转后半部分
        second_half = self.reverseList(slow.next)
        
        # 比较两部分
        first_half = A
        temp = second_half  # 保存起点以便恢复
        result = True
        
        while second_half:
            if first_half.val != second_half.val:
                result = False
                break
            first_half = first_half.next
            second_half = second_half.next
            
        # 恢复链表结构（可选）
        slow.next = self.reverseList(temp)
        
        return result
        
    def reverseList(self, head):
        prev = None
        curr = head
        
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
            
        return prev

# 测试代码
def test():
    # 创建测试链表: 1->2->2->1
    class ListNode:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next
            
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(2)
    head.next.next.next = ListNode(1)
    
    solution = PalindromeList()
    print("Is palindrome:", solution.chkPalindrome(head))

if __name__ == "__main__":
    test()

算法及复杂度

算法：快慢指针 + 链表反转
时间复杂度： $\mathcal{O(n)}$
空间复杂度： $\mathcal{O(1)}$