234. 回文链表

234. 回文链表

难度简单1111 收藏 分享 切换为英文 接收动态 反馈

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

image

<pre style="box-sizing: border-box; font-size: 13px; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgba(var(--dsw-fill-tertiary-rgba)); padding: 10px 15px; color: rgba(var(--grey-9-rgb),1); line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">输入：head = [1,2,2,1]
输出：true
</pre>

示例 2：

image

<pre style="box-sizing: border-box; font-size: 13px; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgba(var(--dsw-fill-tertiary-rgba)); padding: 10px 15px; color: rgba(var(--grey-9-rgb),1); line-height: 1.6; border-radius: 3px; white-space: pre-wrap; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">输入：head = [1,2]
输出：false
</pre>

提示：

• 链表中节点数目在范围[1, 10<sup>5</sup>] 内
• 0 <= Node.val <= 9

思路：
先用快慢指针找到中间节点，然后从中间节点翻转后面到链表，
然后head和mid开始对比，如果都相同，是回文链表

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        if(head.next.next == null) return head.val == head.next.val;
        ListNode mid = middleNode(head);
        ListNode rHead = reverseList(mid.next);
        ListNode lHead = head;
        while(rHead != null){
            if(lHead.val != rHead.val) return false;
            rHead = rHead.next;
            lHead = lHead.next;
        }
        return true;
    }
//查找中间节点
    private ListNode middleNode(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
//翻转链表
    private ListNode reverseList(ListNode head){
        ListNode newHead = null;
        while(head != null){
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }
}