回文链表
最开始的判断
if(head == null || head.next == null){
return true;
}
定义指针
fast为快指针,slow为慢指针,pre为slow前面的指针,作用是用来隔绝中间节点
//定义快慢指针
ListNode fast = head , slow = head ,pre = null;
while(fast !=null && fast.next != null){
fast = fast.next.next;
pre = slow;
slow = slow.next;
}
第二步,需要分奇偶来判断
1-2-3-3-2-1
当节点为偶数的时候,那么slow为第二个3,pre为第一个3,pre.next= null就是将前半部分和后半部分隔开。
当节点为奇数的时候,1-2-3-2-1。slow指向的是3,pre指向的是2,那么我们需要将3给孤立起来,只用反转2-1然后再比较。
if(fast == null){
// odd numbers of nodes
pre.next = null;
slow = reverse(slow);
while(head != null){
if(head.val != slow.val) return false;
head = head.next;
slow = slow.next;
}
return true;
}else{
//奇数个
pre.next = null;
ListNode next = slow.next;
slow.next = null;
next = reverse(next);
while(head != null){
if(head.val != next.val) return false;
head = head.next;
next = next.next;
}
return true;
}
第三步:写出反转函数
1-2-3进行反转。
首先定义一个空节点,让pre<- head 往后移动。知道head==null就停止。最后返回3-2-1。反转成功。
public ListNode reverse(ListNode head){
ListNode pre = null;
while(head != null){
ListNode next = head.next; // 1-2-3 中的2
head.next = pre;
pre = head;
head = next;
}
return pre;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁