回文链表 | Nameless Site

来自Leetcode第234题回文链表

请判断一个链表是否为回文链表。

示例 1:

1 2	输入: 1->2 输出: false

.equals

这种题目其实之前就做过了，但是很明显还是忘了，用了O(n)的空间复杂度来存储整个链表的内容，但是发现在比对的时候，如果直接用!=得到的结果是.equals()是不一样的，!=得不到正确的运行结果。

这里补充一下.equals()和!=的区别

equals是判断两个变量或者实例指向不同内存空间的值是不是相同

而==是判断两个变量或者实例是不是指向同一个内存空间

举个通俗的例子来说，==是判断两个人是不是住在同一个地址，而equals是判断不同地址里住的人是不是同一个

在这题中，有一个测试用例为-129，首先看一下Integer的源码

high的值为127，low的值为-128，当进行这个方法时如果值在-128-127之间，返回的值也就是地址是相同的，因而用!=这个测试用例自然就过不了了。

public boolean isPalindrome(ListNode head) {
    if(head == null)
        return true;
    ListNode p1 = head;
    LinkedList<Integer> ans = new LinkedList<>();

    while(p1 != null){
        ans.addLast(p1.val);
        p1 = p1.next;
    }
    while(ans.size() > 1){
        if(!ans.removeFirst().equals(ans.removeLast()))
            return false;
    }
    return true;
}

翻转链表比对

避免使用 O(n) 额外空间的方法就是改变输入。

我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，因为使用该函数的人不希望链表结构被更改。

算法：

我们可以分为以下几个步骤：

找到前半部分链表的尾节点。
反转后半部分链表。
判断是否为回文。
恢复链表。
返回结果。

执行步骤一，我们可以计算链表节点的数量，然后遍历链表找到前半部分的尾节点。

或者可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针到链表的中间。通过慢指针将链表分为两部分。

若链表有奇数个节点，则中间的节点应该看作是前半部分。

步骤二可以使用在反向链表问题中找到解决方法来反转链表的后半部分。

步骤三比较两个部分的值，当后半部分到达末尾则比较完成，可以忽略计数情况中的中间节点。

步骤四与步骤二使用的函数相同，再反转一次恢复链表本身。

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null)
            return true;
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //从slow后面的链表逆序
        ListNode node = slow.next;
        ListNode curNode = node;
        slow.next = null;
        ListNode pre = null;
        ListNode nextNode = null;
        while(curNode != null){
            nextNode = curNode.next;
            curNode.next = pre;
            pre = curNode;
            curNode = nextNode;
        }
        ListNode temp = head;
        boolean flag = true;
        while(pre != null){
            if(temp.val != pre.val){
                flag = false;
                break;
            }
            temp = temp.next;
            pre = pre.next;
        }
        return flag;
    }
}

补充一下快慢指针：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        ListNode pre = null, temp;
        //在通过快慢双指针找中点的时候完成对前半部分链表的翻转
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            temp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = temp;
        }
        //此时slow就是中间节点
        //如果fast==null则是偶数节点，fast.next == null这是奇数
        fast = fast == null ? slow : slow.next;
        slow = pre;
        while(fast != null && slow != null) {
            if(fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
}

数学方法

从头到尾和从尾到头比对

equals 默认是比较地址的
但是string重写了equals方法，让他比较内容
stringbuffer和stringbuilder并没有重写equals方法，所以比较的是地址
只有string可以比较内容

public boolean isPalindrome(ListNode head) {
    if(head == null)
        return true;
    ListNode p1 = head;
    StringBuilder s1 = new StringBuilder();
    StringBuilder s2 = new StringBuilder();

    while(p1 != null){
        s1.append(p1.val);
        s2.insert(0,p1.val);
        p1 = p1.next;
    }
    return s1.toString().equals(s2.toString());
}