备战蓝桥杯————如何判断回文链表

小小程序员

发布于 2024-02-28 08:22:41

740

发布于 2024-02-28 08:22:41

文章被收录于专栏：小小程序员——DATA小小程序员——DATA

如何判断回文链表

题目描述

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

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

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

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

解题思路及代码

使用快慢指针法找到链表的中间节点，快指针每次走两步，慢指针每次走一步，当快指针到达链表尾部时，慢指针恰好到达中间节点。
根据是否有偶数个节点，将慢指针指向下一个节点，以确保慢指针指向后半部分链表的起始节点。
将后半部分链表反转。
逐一比较前半部分链表和反转后的后半部分链表的节点值，如果全部相同，则链表是回文的，否则不是。

/**
 * 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 {
    boolean isPalindrome(ListNode head) {
    ListNode slow, fast;
    slow = fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    if (fast != null)
        slow = slow.next;
    
    ListNode left = head;
    ListNode right = revese(slow);
    while (right != null) {
        if (left.val != right.val)
            return false;
        left = left.next;
        right = right.next;
    }
    
    return true;
}

    public ListNode revese(ListNode head){
        ListNode pre=null,cur=head,next=head;
        while(cur!=null){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
}