回文链表
请判断一个链表是否为回文链表。
示例 1:
示例 2:
1
2
|
输入: 1->2->2->1
输出: true
|
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解法一：
找到链表的中点，反转后面的链表，然后再遍历两个链表判断是否相等。
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
38
|
public boolean isPalindrome(ListNode head) {
if(head==null||head.next==null){
return true;
}
ListNode p= findin(head);
p.next= fz(p.next);
ListNode re=p.next;
while(head!=null&&re!=null&&re.val==head.val){
head=head.next;
re=re.next;
}
return re==null;
}
//找链表的中点
public static ListNode findin(ListNode head){
if(head == null || head.next == null) {
return head;
}
ListNode p=head;
ListNode q=head;
//判断指针q的下一个是否为空，q的后两步是否为空
while(q.next!=null&&q.next.next!=null){
p=p.next;
q=q.next.next;
}
return p;
}
//反转链表
public static ListNode fz(ListNode head){
if (head==null||head.next==null){
return head;
}
ListNode p=fz(head.next);
head.next.next=head;
head.next=null;
return p;
}
|
解法二：
近期评论