回文链表

定义与背景

回文结构是一种对称结构，在日常生活中广泛存在，如句子“上海自来水来自海上”或数字串12321等。在计算机科学中，链表是常用的数据结构之一。当一个链表的结点值按顺序排列后与其逆序排列相同，则我们称之为回文链表。

回文链表概述

问题描述

给定一个单链表，判断其是否为回文链表。具体来说，需要检查从头到尾遍历和从尾到头遍历的结果是否一致。

实现思路

解决这个问题通常可以采用多种方法，但最常用的有以下几种：

1. 使用额外空间：最直观的方法是将链表的值存入一个数组中，然后用双指针法检查数组是否为回文。
2. 反转一半链表：这种方法不需要额外的空间。首先找到链表的中间位置，再将前半部分链表反转，最后比较前后两部分是否相同。

实现代码

下面是一个使用Python实现的例子：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head: ListNode) -> bool:
    # 辅助函数，反转链表前半部分
    def reverseFirstHalf(current, prev):
        if not current or not current.next:
            return (prev, current)
        new_next, last_node = reverseFirstHalf(current.next, current)
        current.next = prev
        return (new_next, last_node)

    # 辅助函数，检查回文
    def checkPalindrome(left: ListNode, right: ListNode) -> bool:
        while left and right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

    dummy_head = ListNode(0)
    dummy_head.next = head
    slow, fast = dummy_head, head
    
    # 快慢指针找到链表中间位置
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next

    # 反转前半部分链表
    prev, _ = reverseFirstHalf(slow, None)

    # 检查回文
    result = checkPalindrome(prev, head)
    
    # 还原链表结构
    _, last_node = reverseFirstHalf(slow, None)
    return result

# 示例用法
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(2)
node4 = ListNode(1)

node1.next = node2
node2.next = node3
node3.next = node4

print(isPalindrome(node1))  # 输出: True

复杂度分析

• 时间复杂度：O(n)，其中n是链表的长度。
• 空间复杂度：使用了常数级额外空间，除了输入。

总结与思考

通过解决回文链表的问题，我们可以更好地理解链表和数组的操作方式。同时，这个问题也是算法中一个很好的练习题，有助于提高我们的数据结构及算法设计能力。对于实际应用而言，在需要快速判断或调整特定结构时，掌握这些问题的解决方案将大有裨益。

互动提示

尝试修改上述代码，例如添加异常处理机制或者增加对特殊情况（如空链表）的支持，看看能否找到更多的解题思路和方法。