Leetcode刷题日记-234. 回文链表

中心思想：快慢指针

• fast指针每次走两步，slow每次走一步，那么当fast走到最后的时候，slow刚好走到中间
• 从中间开始反转后面的链表，然后比较

//反转链表比较法

class Solution {
    public static boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null){
            return true;
        }
        //快慢指针，寻找中心点
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode star = head;
        ListNode end = slow;
        ListNode newre = resver(slow);
        //反转后比较
        while(star!=end){
            if(star.val!=newre.val){
                return false;
            }
            star=star.next;
            newre=newre.next;
        }
        return true;

    }

//反转链表
    public static ListNode resver(ListNode head){
        if(head==null||head.next==null){
            return head;
        }
        ListNode res = resver(head.next);
        head.next.next=head;
        head.next=null;
        return res;
    }
}
           

另一种方法：

//集合+指针法
class Solution {
    public static boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null){
            return true;
        }else{
            ListNode temp = head;
            List<Integer> list = new ArrayList<>();

            while(temp!=null){
                list.add(temp.val);
                temp=temp.next;
            }
            int index1 = 0;
             int index2=0;
            if(list.size()%2==0){
                index2 = list.size()/2;
            }else{
               index2 = list.size()/2+1;
            }
            for(int i=index2;i<=list.size()-1;i++){
                    index1=list.size()-1-i;
                    if(!list.get(index1).equals(list.get(i))){
                        return false;
                    }
                }
                return true;
        }
    }
}