LeetCode/234. 回文链表

234. 回文链表

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

示例1:

输入: 1->2
输出: false

示例 2:

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

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题解：

转换为数组

本题是非常经典的链表的题目，通过多种方法可以很好地训练思维。一般判断字符串是不是回文的非常容易，就是双指针法，一个指向头，一个指向尾，同时向中间遍历，如果不等直接返回false即可，链表我们也可以用相同的思路，将链表转换为数组然后进行判断

具体代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode currNode = head;
        List<Integer> list = new ArrayList<>();
        //将所有的节点存储到数组中
        while (currNode != null) {
            list.add(currNode.val);
            currNode = currNode.next;
        }

        //两个指针，一个指向头，一个指向尾，然后向中间遍历
        int i = 0, j = list.size() - 1;
        while (i <= j) {
            //这里Integer不能直接比较
//            if (list.get(i) != list.get(j))
            if (!list.get(i).equals(list.get(j))) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

栈

当然，利用栈的后进先出的特点，我们也可以达到目的

具体代码如下：

/**
 * 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)
            return true;

        //创建一个栈将所有节点压入
        Deque<Integer> stack = new ArrayDeque<>();
        ListNode curr = head;
        while (curr != null) {
            stack.push(curr.val);
            curr = curr.next;
        }

        //一个从头节点开始，一个从尾节点开始，比较两个节点的值是否相同
        //当然这里也可以设置一个变量记录链表的长度，这样只需要比较栈中一半的元素即可
        while (head != null) {
            if (head.val != stack.pop())
                return false;
            head = head.next;
        }
        return true;
    }
}

递归

一般的递归都可以改成栈的迭代方法，这里同样可以借助栈的思想来完成递归，具体思路大同小异。我们不断地递归直到链表的尾部停止，然后和另一个头节点进行比较，如果相等，则头节点后移，而递归栈中自然而然的返回尾节点的前一个节点，如果不等则返回false

具体代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    ListNode temp;

    public boolean isPalindrome(ListNode head) {
        temp = head;
        return help(head);
    }

    private boolean help(ListNode node) {
        if (node == null)
            return true;

        //不断地递归直到链表的尾部
        boolean flags = help(node.next) && (temp.val == node.val);
        //从前往后遍历的指针后移
        temp = temp.next;
        return flags;
    }
}

快慢指针

快慢指针思想很妙，但是本题中需要改变链表结构，而且官方也说了，实际工程中，如果多线程的话这种方法也不能使用。快慢指针的具体思想就是利用一快一慢指针找到链表的中点，然后将后半部分的链表翻转，这样一个指针从头开始，一个指针从尾开始进行遍历，遇到值不相同的就返回false

具体代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode quick = head;
        ListNode slow = head;
        while (quick != null && quick.next != null) {
            quick = quick.next.next;
            slow = slow.next;
        }
        //这里说明节点个数为偶数个，需要将slow指向中间两个节点的后一个节点
        if (quick != null) {
            slow = slow.next;
        }

        ListNode tail = reverse(slow);

        //判断链表是否是回文链表
        while (tail != null) {
            if (head.val != tail.val)
                return false;
            head = head.next;
            tail = tail.next;
        }
        return true;
    }

    //翻转链表，这里注意需要一个临时节点存放curr的下一个节点，不然链表会断开
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;
    }
}