回文比较

步骤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;
       }