234. 回文链表（java实现）--2种解法（双指针，反转链表后半段）LeetCode

题目：解法1：双指针解法2：反转链表后半段

01：递归02：不设置前驱节点03：设置前驱节点

    
    public static boolean isPalindrome(ListNode head) {
        ArrayList list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        return judge_doublePoint(list);
    }


    private static boolean judge_doublePoint(ArrayList list) {
        int l = 0, r = list.size() - 1;
        while (r > l) {
            if (!list.get(l++).equals(list.get(r--))) {
                return false;
            }
        }
        return true;
    }

时间复杂度：On

空间复杂度：On

    
    public static boolean isPalindrome(ListNode head) {
        ListNode slow=head,fast=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
    
        ListNode reverse_half = reverse_recursive(slow);
    //    ListNode reverse_half = reverse_noPre(slow);
    //    ListNode reverse_half = reverse_pre(slow);

        while (reverse_half!=null){
            if (reverse_half.val!=head.val){
                return false;
            }
            reverse_half=reverse_half.next;
            head=head.next;
        }
        return true;
    }
    
    private static ListNode reverse_recursive(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode tail = reverse_recursive(head.next);
        head.next.next=head;
        head.next=null;
        return tail;
    }

时间复杂度：On

空间复杂度：On

    private static ListNode reverse_noPre(ListNode head) {
        ListNode curr = head;
        ListNode next = curr.next;
        while (next!= null){
            ListNode nn = next.next;
            next.next=curr;
            head.next=nn;
            curr=next;
            next=nn;
        }
        return curr;
    }

时间复杂度：On

空间复杂度：O1

    private static ListNode reverse_pre(ListNode reversNode) {
        ListNode pre=null;
        ListNode curr = reversNode;
        while (curr!=null){
            ListNode next = curr.next;
            curr.next=pre;
            pre=curr;
            curr=next;
        }
        return pre;
    }

时间复杂度：On

空间复杂度：O1