回文链表
题目要求
你需要编写一个算法来判断一个单链表是否为回文结构。所谓回文链表，指的是这个链表的元素从前往后读和从后往前读是完全相同的。例如，链表 1->2->2->1 是回文的，而链表 1->2->3 不是。
解题思路
要判断一个链表是否为回文，我们可以采取以下步骤：
-
找到中点：首先，我们需要找到链表的中点。这可以通过快慢指针的方法来实现。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针就位于链表的中点。
-
链表后半部分反转：当我们找到链表的中点后，将链表的后半部分进行反转。这样我们就可以很容易地从中点向两边比较，判断是否为回文。
-
比较前后两半：从中点开始，将前半部分和反转后的后半部分进行元素比较。如果所有元素都相同，则链表是回文的。否则，不是。
-
恢复链表（可选）：如果需要保持链表的原始结构，可以再次反转链表的后半部分，恢复链表的原始结构。
-
返回结果：根据比较的结果，返回 true 或 false。
这个方法的时间复杂度是 O(n)，空间复杂度是 O(1)，因为我们只需要改变一些指针的指向，而不需要分配任何额外的存储空间来存储链表的值。
Golang 版本
type ListNode struct {
Val int
Next *ListNode
}
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
// 快慢指针寻找中点
slow, fast := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
// 反转后半部分链表
slow.Next = reverseList(slow.Next)
// 保存中点之后的链表，用于最后恢复链表
secondHalfStart := slow.Next
// 比较前半部分和反转后的后半部分
p1 := head
p2 := slow.Next
result := true
for result && p2 != nil {
if p1.Val != p2.Val {
result = false
}
p1 = p1.Next
p2 = p2.Next
}
// 恢复链表（如果需要）
slow.Next = reverseList(secondHalfStart)
return result
}
// 反转链表函数
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
curr := head
for curr != nil {
nextTemp := curr.Next
curr.Next = prev
prev = curr
curr = nextTemp
}
return prev
}
这段代码定义了一个ListNode结构体，实现了一个isPalindrome函数来检查链表是否为回文。它首先使用快慢指针找到链表的中点，然后反转中点之后的链表部分，接着比较前半部分和反转后的后半部分是否相同。最后，它还包含了一个可选的步骤来恢复链表的原始结构。
C++版本
#include <iostream>
// 定义链表节点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) return true;
// 快慢指针找到中点
ListNode *slow = head, *fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
// 反转后半部分链表
slow->next = reverseList(slow->next);
ListNode* secondHalfStart = slow->next;
// 比较前半部分和反转后的后半部分
ListNode *p1 = head;
ListNode *p2 = secondHalfStart;
bool result = true;
while (result && p2 != nullptr) {
if (p1->val != p2->val) result = false;
p1 = p1->next;
p2 = p2->next;
}
// 恢复链表（如果需要）
slow->next = reverseList(secondHalfStart);
return result;
}
private:
ListNode* reverseList(ListNode* head) {
ListNode *prev = nullptr, *curr = head, *next = nullptr;
while (curr != nullptr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};
这段 C++代码定义了一个ListNode结构体和一个Solution类。Solution类中的isPalindrome成员函数用于检查链表是否为回文。它首先使用快慢指针技术找到链表的中点，然后反转中点之后的链表部分，接着比较前半部分和反转后的后半部分是否相同。最后，它还包含了一个可选的步骤来恢复链表的原始结构。reverseList是一个私有成员函数，用于反转链表。
Python 版本
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head or not head.next:
return True
# 快慢指针找到中点
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 反转后半部分链表
prev = None
while slow:
tmp = slow.next
slow.next = prev
prev = slow
slow = tmp
# 比较前半部分和反转后的后半部分
left, right = head, prev
while right: # 只需比较后半部分
if left.val != right.val:
return False
left, right = left.next, right.next
return True
这段 Python 代码定义了一个ListNode类用于表示链表节点，以及一个Solution类，其中包含了一个isPalindrome方法用于判断链表是否为回文。该方法首先使用快慢指针找到链表的中点，然后反转中点之后的链表部分，最后比较前半部分和反转后的后半部分是否相同。如果相同，则链表是回文的，返回True；否则，返回False。
Java 版本
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// 快慢指针找到中点
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 反转后半部分链表
slow = reverseList(slow);
fast = head;
// 比较前半部分和反转后的后半部分
while (slow != null) {
if (fast.val != slow.val) {
return false;
}
fast = fast.next;
slow = slow.next;
}
return true;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
这段 Java 代码定义了一个ListNode类用于表示链表节点，以及一个Solution类，其中包含了一个isPalindrome方法用于判断链表是否为回文。该方法首先使用快慢指针找到链表的中点，然后反转中点之后的链表部分，最后比较前半部分和反转后的后半部分是否相同。如果相同，则链表是回文的，返回true；否则，返回false。reverseList是一个辅助方法，用于反转链表。
Rust 版本
#![allow(unused)] fn main() { // Definition for singly-linked list. #[derive(PartialEq, Eq, Clone, Debug)] pub struct ListNode { pub val: i32, pub next: Option<Box<ListNode>>, } impl ListNode { #[inline] fn new(val: i32) -> Self { ListNode { next: None, val, } } } pub struct Solution; impl Solution { pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool { let mut values = Vec::new(); let mut current = head.as_ref(); while let Some(node) = current { values.push(node.val); current = node.next.as_ref(); } let mut front = 0; let mut back = values.len() - 1; while front < back { if values[front] != values[back] { return false; } front += 1; back -= 1; } true } } }
这段 Rust 代码定义了一个ListNode结构体用于表示链表节点，并实现了一个Solution结构体，其中包含了一个is_palindrome函数用于判断链表是否为回文。该函数首先将链表的值复制到一个向量中，然后使用双指针法在向量上从两端向中间遍历，比较对应的值是否相等。如果所有对应的值都相等，则链表是回文的，函数返回true；否则，返回false。
总结
上面给出的解法是用不同编程语言实现的判断链表是否为回文的算法。这些解法的共同思路是：
- 使用快慢指针找到链表的中点。
- 反转链表的后半部分。
- 比较前半部分和反转后的后半部分是否相同。
这些解法在实现细节上有所不同，比如在反转链表部分的实现方式上，以及在处理链表节点的方式上。但它们的核心思想是一致的，都是基于快慢指针和链表反转来判断链表是否为回文。