234. Palindrome Linked List

Link

Solution

策略是 1.把list分成兩半 (透過slow, fast pointer完成) 2. 將後半段reverse (透過206) 3. 這兩半理論上要一模一樣

 public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast != null){ //fast.next == null
            //     slow
            //      ^
            //1->2->3->4->5
            //            ^ fast 
            
            slow = slow.next;
            
        }
        slow = reverse(slow);
        fast = head;
        while(slow != null){
            if(fast.val != slow.val){
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
    
    public ListNode reverse(ListNode node){
        ListNode prev = null;
        while(node != null){
            ListNode next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        return prev;
    }