LeetCode 234. 回文链表
题目描述
思路分析
- 获取链表的中间节点
- 反转链表的后半部分
- 比较
参考代码
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
36
37
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
slow, fast := head, head
var pre *ListNode
for fast != nil && fast.Next != nil {
pre = slow
slow = slow.Next
fast = fast.Next.Next
}
pre.Next = nil
l1, l2 := head, reverse(slow)
for l1 != nil {
if l1.Val != l2.Val {
return false
}
l1 = l1.Next
l2 = l2.Next
}
return true
}
func reverse(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
var pre *ListNode
cur := head
for cur != nil {
node := cur.Next
cur.Next = pre
pre = cur
cur = node
}
return pre
}
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
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;
}
ListNode pre = null, cur = slow;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
ListNode p1 = head, p2 = pre;
while (p2 != null) {
if (p1.val != p2.val) {
return false;
}
p1 = p1.next;
p2 = p2.next;
}
return true;
}
}
相似题目
题目 | 难度 | 题解 |
---|---|---|
回文数 | Easy | |
验证回文串 | Easy | |
反转链表 | Easy |
CC BY-NC-SA 4.0
许可协议,转载请注明出处!
本博客所有文章除特别声明外,均采用