public class Hello {    public static void main(String[] args) {        ListNode head=new ListNode(0);        ListNode head1=new ListNode(1);        ListNode head2=new ListNode(2);        ListNode head3=new ListNode(1);        ListNode head4=new ListNode(2);        #region        ListNode head5=new ListNode(1);        ListNode head6=new ListNode(0);        head5.next=head6;        head4.next=head5;        #endregion        head3.next=head4;        head2.next=head3;        head1.next=head2;        head.next=head1;                Solution0 s =new Solution0();        boolean res=s.isPalindrome(head);        System.out.println(res);                // while(head!=null){        //     System.out.println(head.val);        //     head=head.next;        // }                                    }}class ListNode {    int val;    ListNode next;    ListNode(int x) { val = x; }  }class Solution0 {    public boolean isPalindrome(ListNode head) {        if (head == null || head.next == null)            return true;        if (head.val == head.next.val && head.next.next == null)            return true;        ListNode slow = head;        ListNode cur = head.next;        while (cur.next != null) {            if (slow.val == cur.next.val) {                if (cur.next.next != null)                    return false;                cur.next = null;                slow = slow.next;                cur = slow.next;                                    if (cur == null || slow.val == cur.val)                    return true;            } else {                cur = cur.next;            }        }        return false;    }}class Solution1 {    public boolean isPalindrome(ListNode head) {        if (head == null) return true;        // detect the length        int len = 0;        for (ListNode p = head; p != null; p = p.next) len++;        // reverse the first half list        ListNode p = head, q = null, r = p.next;        for (int i = 0; i < len / 2; i++) {            p.next = q;            q = p;            p = r;            r = r.next;        }        // detect the palindrome from the mid        r = len % 2 == 0 ? p : r;        while (r != null && q != null) {            if (r.val != q.val) return false;            r = r.next;            q = q.next;        }        return r == null && q == null;    }}

以上两个代码都不是我写的，leetcode上别人提交的java代码。

Solution0 是最快的代码，0ms。

Solution1其次，1ms。

 

我看S0的时候有两个问题。

Q1：不正确。

Q2：不是O(n)，而是O(n²).

 

Q1：我本地测试。

出了一组数据，0-1-2-1-2-1-0

S0 返回false，S1 返回true。

可以认为leetcode的数据回文链表中同一个数最多只出现两次。

 

但是Q2我还是不懂。虽然写的是一层循环，但实际上相当于两层循环，和普通的选择排序一样。

 

---

 

 

public class Solution {        ListNode temp;        /**     * 测试链表是否为回文链表     * @param head 链表首节点     * @return     */    public boolean isPalindrome(ListNode head) {        temp = head;        return isPalindromeList(head);     }        /**     * 测试链表是否为回文链表     * @param node 链表首节点     * @return     */    private boolean isPalindromeList(ListNode node) {        if (node == null) {            return true;        }        boolean result = isPalindromeList(node.next) && (temp.val == node.val);        temp = temp.next;        return result;    }}

https://my.oschina.net/Tsybius2014/blog/547537

递归，4ms。

 

 

 

 

---

 

差不多是个废人了。

->val 忘了加“-”，报了几次错没看到后面（因为一行写了两个->val）。

我还在想，明明前几行也用了，怎么没错。

 

然后还在纠结while 循环和外面的返回

 

最后还TLE了。

 

现在发现我这样写和原来的一样是错的

 

 

 

 

 

 

---

 

class Solution {    public boolean isPalindrome(ListNode head) {        int lhash = 0, rhash = 0;        for(int x = 1; head != null; head = head.next, x *= 31) {            lhash = lhash*31 + head.val;                        rhash = rhash + head.val*x;        }                return lhash == rhash;    }}

 

 

讨论区的。hash判断，神仙操作，看不懂。