题目描述补充

题目：回文链表

给定一个单链表，请编写一个函数来判断该链表是否为回文链表。回文链表是指从前往后读和从后往前读都一样的链表。

示例 1:

输入: 1->2
输出: false

示例 2:

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

进阶：

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

PHP 示例代码

<?php

class ListNode {
    public $val = 0;
    public $next = null;

    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function isPalindrome($head) {
    if ($head == null || $head->next == null) {
        return true;
    }

    // 使用快慢指针找到链表的中点
    $slow = $head;
    $fast = $head;
    while ($fast->next != null && $fast->next->next != null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
    }

    // 反转后半部分链表
    $secondHalf = reverseList($slow->next);

    // 比较前半部分和反转后的后半部分
    $p1 = $head;
    $p2 = $secondHalf;
    while ($p2 != null) {
        if ($p1->val != $p2->val) {
            return false;
        }
        $p1 = $p1->next;
        $p2 = $p2->next;
    }

    // （可选）恢复链表原状（如果题目不要求，可以省略）
    // $slow->next = reverseList($secondHalf);

    return true;
}

function reverseList($head) {
    $prev = null;
    $curr = $head;
    while ($curr != null) {
        $nextTemp = $curr->next;
        $curr->next = $prev;
        $prev = $curr;
        $curr = $nextTemp;
    }
    return $prev;
}

// 测试代码
$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(2);
$head->next->next->next = new ListNode(1);

echo isPalindrome($head) ? "true" : "false"; // 输出 true
?>

Python 示例代码

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

def isPalindrome(head):
    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 = reverse_list(slow.next)

    # 比较前半部分和反转后的后半部分
    p1, p2 = head, second_half
    while p2:
        if p1.val != p2.val:
            return False
        p1 = p1.next
        p2 = p2.next

    return True

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

# 测试代码
head = ListNode(1, ListNode(2, ListNode(2, ListNode(1))))
print(isPalindrome(head))  # 输出 True

JavaScript 示例代码

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

function isPalindrome(head) {
    if (!head || !head.next) return true;

    let slow = head;
    let fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    let secondHalf = reverseList(slow.next);

    let p1 = head;
    let p2 = secondHalf;
    while (p2) {
        if (p1.val !== p2.val) return false;
        p1 = p1.next;
        p2 = p2.next;
    }

    return true;
}

function reverseList(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

// 测试代码
let head = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(1))));
console.log(isPalindrome(head)); // 输出 true

码小课网站中有更多相关内容分享给大家学习，希望这些示例能帮助你理解并解决回文链表的问题。