PalindromeLinkedList [source code]

public class PalindromeLinkedList {
static
/******************************************************************************/
public class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) {
            slow = slow.next;
        }
        slow = reverse(slow);
        while (head != null && slow != null) {
            if (head.val != slow.val) return false;
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PalindromeLinkedList.Solution tester = new PalindromeLinkedList.Solution();
        int N = 11;
        int half = N % 2 == 0 ? N / 2 - 1 : N / 2;
        ListNode[] nodes = new ListNode[N];
        for (int i = 0; i <= half; i++) {
            nodes[i] = new ListNode(i);
        }
        for (int i = N - 1; i >= 0 && nodes[i] == null; i--) {
            nodes[i] = new ListNode(N - 1 - i);
        }
        for (int i = 0; i < N - 1; i++) nodes[i].next = nodes[i + 1];
        ListNode head = nodes[0];
        System.out.println(tester.isPalindrome(head));
    }


}

不要急着立刻就想 Follow-Up, 先想笨办法;

这题的笨办法比较简单, 直接走一遍, 全部放到一个 array 里面, 然后array 里面就好解决了;
一个比较 naive 的想法是把 ListNode 给 wrap 到一个DoublyLinkedList的 node 里面, 不过这样好像应该还是算有额外空间的;

总结一下寻找O(1) space 的一般思路:

1. recursion: 因为一般recursion stack不算是extra space;
2. pattern 题, 这个不用说的;
3. bit manipulation;
4. InPlace 操作: 这一题就是这样;
5. historical stream: 而且并不是所有的历史流都可以做到O(1)空间, 只有一些特殊的, 比如某些特殊的 DP, 可以做到; 或者类似moore voting这样的;

这题最起码你要学完的一个地方就是 reverse 的 iterative 写法要写的非常熟练了;
另外我目前有一个隐约的感觉, 好像涉及到 LinkedList 的题目, 就那么几个常规操作, 包括 reverse. 感觉把相关的题目多做一点之后应该会熟悉一些;

另外这里一个快慢指针找终点的方法也可以稍微学习一下; 这个做法的好处就是不用专门跑一遍来找 size: how to find the median in O(N) time without knowing the size;

这题的大部分思路都是依靠 reverse, 但是 discussion 里面有一个我个人认为非常聪明的解:

public class Solution {  
    ListNode h;  
    public boolean isPalindrome(ListNode head) {  
        if (head == null) return true;  

        if (h == null) h = head;  

        boolean tmp = true;          
        if (head.next != null) tmp &= isPalindrome(head.next);  

        tmp &= (head.val == h.val);  
        h = h.next;  
        return tmp;  
    }  
}

这个解刚开始我用 recursion 的思路来看它, 其实不是很好理解; 但是这个解如果你用 DFS 的思路来理解, 就好理解的多; 这个问题难写的一个原因就是因为没有办法获得尾巴的信息; 或者general 的说, 没有办法完成一个从尾巴向上回头的问题, 普通的指针 traversal 做不到这一点; 这个人这里用 recursion 的方法就是为了达到一个上行的作用, 可以说这个跟你单独用一个 Stack 来做是差不多的原理(所有路过的全都 push 进去), 不过如果是面试, 这个答案是可以过no extra space的要求的;

这个算法可以提炼出来的一个中心思想就是: 可以用 recursion 来做singly linked list的reversed traversal. 当然你也可以说用 recursion 来做对称分析, 不过不如reversed traversal来的 general;
我个人认为这个算法比直白的reverse list更加的 elegant;

当然他具体的写法上还是有一定的技巧的, 他这里的技巧就是每次退出一个 node 的时候, 这个 global 的 h 都要向下移动一格, 保持对称位置;

这个算法刚开始看到的时候我尝试直接用 recursion 来理解, 就是考虑当前level 的 node 跟自己的两个 child 之间的关系(DP Property), 但是这样考虑了半天好像还是没有用; 最后就只能画 trace, 画 trace 的时候从一个简单的例子开始, 不要想的太复杂1 -> 2 -> 1就可以了, 这个 trace 跑一遍就知道这个算法的核心更多的是接近 DFS 而不是 recursion;

如果非要用recursion来解释, 这里的 DP value 好像可以说是: whether head equals the node in the mirror position; 不过这个只能说有点牵强了, 这个算法还是从imperative 的角度更好理解;

Problem Description

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?

Difficulty:Easy
Total Accepted:107.1K
Total Submissions:329.5K
Contributor: LeetCode
Companies
amazon facebook
Related Topics
linked list two pointers
Similar Questions
Palindrome Number Valid Palindrome Reverse Linked List