链表 - LeetCode 234.回文链表（快慢指针）

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

输入: head = [1,2,3,3,2,1]
输出: true

输入: head = [1,2]
输出: false

解题思路：
第一步：先找链表中位
第二步：反转中位的后半部分链表，得到反转后链表的head
第三步：判断回文

class Solution {
    public boolean isPalindrome(ListNode head) {

 if (head == null) {
            return true;
        }

        // 第一步：先找链表中位
        ListNode leftHalfEnd = middleNode(head);
        // 第二步：反转中位的后半部分链表，得到反转后链表的head
        ListNode rightHalfHead = reverseList(leftHalfEnd.next);
        // 第三步：判断回文
        ListNode p1 = head;
        ListNode p2 = rightHalfHead;
        boolean result = true; // 默认p1、p2指向的节点值相等
        // p2链表节点个数，一定小于等于p1链表节点个数，所以这里条件是 p2 != null
        while(result && p2 != null) {
            if(p1.val != p2.val){
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return result;
    }

    private ListNode middleNode(ListNode head){
        // 设置快慢指针开始都指向head
        ListNode slow = head;
        ListNode fast = head;

        // 同时移动：slow一次一步，fast一次两步
        // 必须保证fast能移动2步时，才移动,所以要判断 fast.next != null && fast.next.next != null
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 最后slow指向节点就是中间节点
        return slow;
    } 

   // 反转链表，返回反转后链表的head
    private ListNode reverseList(ListNode head){
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

画图理解：

• 第一步：先找链表中位
  • 链表节点个数为奇数的情况
  • 链表节点个数为偶数的情况

image.png

此时，slow所指节点就是中位节点。接着进行第二步，反转中位节点后的链表，以奇数链表为例：

image.png

接着，第三步：判断回文。

每次移动都判断当前 P1、P2 指针指向的节点值是否相同。

P2指向节点个数，一定小于等于 P1指向节点个数。

• 如果链表节点个数位奇数， P1节点个数 > P2节点个数 (比如 3 > 2 )
• 如果链表节点个数位偶数， P1节点个数 == P2节点个数 (比如 都是3 )

image.png

• 如果相同就继续移动
• 如果不同，就return false