🌕 234. 回文链表

难度: 🌕

问题描述

---

解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // 思路：
        // 快慢指针找中点
        // 中点处进行链表拆分，成为 2 条链表
        // 稍短的一半修改指针指向，逆序排列
        // 两条新链表双指针从头开始遍历
        // 1. 快慢指针找中点
        // 特殊情况特判
        if(head.next == null) {
            return true;
        }
        // 节点数 > 1
        ListNode slow = head;
        ListNode fast = head.next; // 这样找到的中点 slow 为中点偏左，可以直接拆中点后的连接关系
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow 所在即为中点，切断和后面节点的连接
        ListNode right = slow.next;
        slow.next = null;
        ListNode left = head;
        // 2. right 长度 <= left，right 逆序
        right = reverse(right);
        // 3. 双指针同时遍历
        while(right != null) {
            if(left.val != right.val) {
                return false;
            } else {
                left = left.next;
                right = right.next;
            }
        }
        return true;
    }

    private ListNode reverse(ListNode head) {
        // 特殊情况特判
        if(head == null || head.next == null) {
            return head;
        }
        // 节点数 > 1
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

---

输出