234. Palindrome Linked List.md

234. Palindrome Linked List

Problem

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

tag:

Solution

采用快慢指针找到中间节点，然后反转后半部分链表， 判断两部分链表是否相等，注意奇偶节点。

java

    public boolean isPalindrome(ListNode head) {
        ListNode fast = head,slow = head;
        while(fast!=null&&fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if(fast!=null) slow = slow.next;
        slow = reverseList(slow);
        while(slow!=null && slow.val==head.val) {
            slow = slow.next;
            head = head.next;
        }
        return slow==null;
    }
    
    ListNode reverseList(ListNode head) {
        ListNode pre = null, next = null;
        while(head!=null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

go