回文比较
回文比较
步骤1.找中间点
用到了查找链表中间节点-快慢指针法
public ListNode middleNode (ListNode head){
ListNode p1=head;
ListNode p2=head;
while (p2!=null&&p2.next!=null){
p1=p1.next;
p2=p2.next.next;
}
return p1;
}
步骤2.中间点后半个链表反转
利用插入排序链表
private ListNode reverse(ListNode o1){
ListNode n1=null;//新链表开始为空
while (o1!=null){//如果没有到最后一个
ListNode o2=o1.next;//建立链表o1的下一个
o1.next=n1;//把o1连接到o1
n1=o1;//更新刚刚的o1变成n1
o1=o2;//更新o2变成o1
}
return n1;
}
回文比较
public boolean isPalindrome(ListNode head){
ListNode middle=middleNode(head);//查找中间值
ListNode newHead=reverse(middle);//中间值变成链表的新头
while (newHead!=null){
if(newHead.val!=head.val){//两相比较
return false;
}//相比else提升1ms
newHead=newHead.next;//不断更新
head=head.next;
}
return true;
}
回文比较-升级版
思路:在寻找中间节点的时候就进行排序比较
[1,2,,2,1]
比较前边的
[2,1]
public boolean isPalindrome(ListNode head){
ListNode p1= head;//慢
ListNode p2= head;//快
ListNode n1=null;
ListNode o1=head;
while (p2!=null&&p2.next!=null){
p1=p1.next;
p2=p2.next.next;
//反转链表
ListNode o2=o1.next;
o1.next=n1;
n1=o1;
o1=o2;
}
if(p2!=null){
p1=p1.next;
}
while (n1!=null){
if(n1.val!=p1.val){
return false;
}
n1=n1.next;
p1=p1.next;
}
return true;
}