【LeetCode】【算法】234.回文链表

LeetCode 234.回文链表

题目描述

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

思路

思路：

1. 通过快慢指针找到链表的中间节点
2. 将后半个链表进行反转
3. 比较前半部分和后半部分链表的值是否相等

代码

/**
 * 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) {
        if (head.next == null) return true;
        // 1. 找到链表的中点
        ListNode p1 = head;
        ListNode p2 = head;
        while (p2.next != null && p2.next.next != null){
            p1 = p1.next;
            p2 = p2.next.next;
        }
        // 2. 反转链表
        ListNode prev = p1;
        p1 = p1.next;
        prev.next = null;
        while (p1 != null){
            ListNode tmp = p1.next;
            p1.next = prev;
            prev = p1;
            p1 = tmp;
        }
        // 3. 检查链表是否相同
        p1 = prev;
        p2 = head;
        while (p1 != null && p2 != null){
            if (p1.val != p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }
}