3.回文链表

• 2.10

  • 忘了开头的判断，秒了

• 1.24

  • 这一次用的双指针法，大胆用吧，反转后类似与y 型链表，共享中间节点（如果是奇数）

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next==null) return true;
        ListNode slow = head;
        ListNode fast = head;
        // int count=0;
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode node2 = reverse(slow);
        ListNode node1 = head;
 
        while(node2!=null){
            if(node1.val!=node2.val) return false;
            node1 = node1.next;
            node2 = node2.next;
        }
        return true;
    }

• 1.19

  • 秒了，第二遍做的时候反转那里用的上一节的递归，有点爽
  • 第二遍还是把比较条件算错了

• 不用专门判断链表长度是否为奇偶,while(r!=null&&r.next!=null){将隐式的判断

• 11.9

  • 我这里用的是length/2,可以用
  • 这里对比的ptr.val,而相交列表对比的是ListNode本身

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode ptr = head;
 
        int count=0;
        while(ptr!=null){
            ptr = ptr.next;
            count++;
        }
 
        if(count==1) return true;
 
        ListNode head1 = head;
        ListNode head2 = head;
 
        int lotation =0;
        while(lotation!=count/2){
            head2 = head2.next;
            lotation++;
        }
        ListNode newHead =  reverse(head2);
 
        while(newHead!=null){
            if(head1.val!=newHead.val) return false;
            head1 = head1.next;
            newHead = newHead.next;
        }
        return true;
 
    }
 
    public ListNode reverse(ListNode head){
        if(head==null||head.next==null) return head;
        ListNode newHead = reverse(head.next);
        head.next.next = head;
        head.next=null;
        return newHead; 
    }
}

        int length = 0;
        ListNode ptr = head;
        while(ptr!=null){
            ptr = ptr.next;
            length++;
        }
        // if(length==1) return true;
        ptr = head;
        for(int i=0;i<length/2;i++){
            ptr = ptr.next;
        }
 
 
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode r = head;
        ListNode l = head;
        while(r!=null&&r.next!=null){
            r = r.next;
            l = l.next;
            r = r.next;
        }
        ListNode n =  reverse(l);
        ListNode m = head;
        while(n!=null){
            if(n.val!=m.val){
                return false;
            }
            n = n.next;
            m = m.next;
        }
        return true;
    }
 
    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode currt = head;
        while(currt!=null){
            ListNode next = currt.next;
            currt.next = pre;
            pre = currt;
            currt = next;
        }
        return pre;
    }
}