leetcode 234. 回文链表

题目描述

请判断一个链表是否为回文链表。

示例 1:
输入: 1->2
输出: false

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

题解

分为三步,首先通过快慢指针找到链表的中点,然后算出中点后面的逆序链表,最后比较链表中点前后的值是否相同

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
fast, slow := head, head
var reverse *ListNode
for fast != nil {
slow = slow.Next
if fast.Next != nil {
fast = fast.Next.Next
} else {
fast = fast.Next
}
}

for slow != nil {
tmp := slow.Next
slow.Next = reverse
reverse = slow
slow = tmp
}

for head != nil && reverse != nil {
if head.Val != reverse.Val {
return false
}
head = head.Next
reverse = reverse.Next
}
return true
}