当前位置： 面试刷题>> 回文链表 (经典算法题500道)
### 题目描述补充
**题目：回文链表**
给定一个单链表，请编写一个函数来判断该链表是否为回文链表。回文链表是指从前往后读和从后往前读都一样的链表。
**示例 1**:
```
输入: 1->2
输出: false
```
**示例 2**:
```
输入: 1->2->2->1
输出: true
```
**进阶**：
- 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此问题？
### PHP 示例代码
```php
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 示例代码
```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 示例代码
```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
```
**码小课网站中有更多相关内容分享给大家学习**，希望这些示例能帮助你理解并解决回文链表的问题。