234. Palindrome Linked List

Leetcode Linked List Two Pointers

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

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

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

package com.leetcode;

/**
 * An Palindrome is a sequence of characters
 * which reads the same backward or forward.
 *
 *
 * 这道题目第一让人联想到的就是Leetcode Q206ReverseLinkedList，
 * 即将链表反转，然后一一比对。
 *
 * 在这里，只要将链表的后半部分反转，然后利用两个指针分别指向链表首尾，
 * 依次向前/向后移动指针，直到到达中点。
 *
 * 我觉得这里的难点主要是要考虑一些特殊情况，比如说只有2，3个元素的这种链表。
 *
 */
public class Q234PalindromeLinkedList {
    public static boolean isPalindrome(ListNode head) {
        if ((head == null) || (head.next == null)) {
            return true;
        }

        // find lenth
        int len;
        ListNode pos = head;
        for (len = 0; pos != null; len++) {
            pos = pos.next;
        }

        // find middle node
        ListNode mid = head;
        for (int i = 0; i < (len-1)/2; i++)
            mid = mid.next;

        // reverse
        ListNode cur = mid.next;
        if (cur.next != null) {
            ListNode next;
            for (pos = mid; cur.next != null; ) {
                next = cur.next;
                cur.next = pos;
                pos = cur;
                cur = next;
            }
            cur.next = pos;
        } else {
            cur.next = mid;
        }

        ListNode tail = cur;

        // compare the first and second half nodes
        while (tail != mid) {
            if (tail.val != head.val) {
                return false;
            }
            tail = tail.next;
            head = head.next;
        }

        return  true;
    }

    /**
     * 寻找mid和tail时其实不用计算链表长度
     * 只要有两个指针，一块一慢，遍历链表即可
     */

    public static boolean isPalindromeUsingQuickFindMidTail(ListNode head) {
        if ((head == null) || (head.next == null)) {
            return true;
        }

        // A trick to quickly find mid and tail of linked list
        ListNode mid = head, tail = head.next;
        while ((tail != null) && (tail.next != null)) {
            mid = mid.next;
            tail = tail.next.next;
        }

        // reverse
        ListNode cur = mid.next, pos, next;
        if (cur.next != null) {
            for (pos = mid; cur.next != null; ) {
                next = cur.next;
                cur.next = pos;
                pos = cur;
                cur = next;
            }
            cur.next = pos;
        } else {
            cur.next = mid;
        }

        tail = cur;
        // compare the first and second half nodes
        while (tail != mid) {
            if (tail.val != head.val) {
                return false;
            }
            tail = tail.next;
            head = head.next;
        }
        return  true;
    }
}