当前位置：首页 > article >正文

LeetCode100之回文链表(234)--Java

article 2024/11/18 9:47:22

1.问题描述

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

示例1

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

示例2

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

提示

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

难度等级

简单

题目链接

回文链表

2.解题思路

这道题要求我们判断提供的链表是否为一个回文链表，根据回文的特点，我们不难想到，如何我们将链表反转，然后再来和原链表进行比较，如何是回文链表的话，它们每一个节点的数值应该都是彼此相等的。

经过上面的分析，我们现在需要做的就是得到链表的反转链表。要注意的是，这里我们要的反转链表不能对原链表进行原地操作(与LeetCode另一道反转链表的题目不同)，每一个节点都需要分配新的内存，否则，我们其实只是把原链表进行了反转，而不是得到两条方向不同的链表。

反转链表很简单，我们只需要定义一个新的头结点指针，已经一个保存已经反转后的链表头指针和一个原来链表的遍历指针即可。

        //存储当前节点
        ListNode cur = head;
        //新的头结点
        ListNode newHead = null;
        //已经反转好的链表头指针
        ListNode pre = null;

反转链表的四个步骤:

创建一个新的头结点，并将头结点的值赋值为原链表当前指针所指节点的值。

            //新链表头
            newHead = new ListNode(cur.val);

将新的头结点的next指针指向已经反转好的链表头节点，增长反转链表。

            //将链表头的next指针指向已经反转好的链表
            newHead.next = pre;

将已经反转好的链表头结点指针指向当前的新头结点。

            //更新已经反转好的链表头指针
            pre = newHead;

移动遍历链表的指针。

           //更新当前指针
            cur = cur.next;

重复上述四步，直到原链表被遍历完为止。然后将新的反转链表头结点返回即可。

得到了反转后的链表之后，我们只需要将反转链表与原链表的每个节点进行一一比对，一旦出现一个不同的节点，说明不是回文链表，直接返回false，若将两个链表比对完之后，没有发现不同，说明是回文链表，直接返回true即可。

        //原链表指针
        ListNode p1 = head;
        //反转链表指针
        ListNode p2 = reverse(head);
        while(p1 != null && p2 != null){
            //判断是否相等
            if(p1.val != p2.val){
                return false;
            }
            //移动
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;

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) {
        //原链表指针
        ListNode p1 = head;
        //反转链表指针
        ListNode p2 = reverse(head);
        while(p1 != null && p2 != null){
            //判断是否相等
            if(p1.val != p2.val){
                return false;
            }
            //移动
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }
    public ListNode reverse(ListNode head){
        //存储当前节点
        ListNode cur = head;
        //新的头结点
        ListNode newHead = null;
        //已经反转好的链表头指针
        ListNode pre = null;
        //获取反转的新链表
        while(cur != null){
            //新链表头
            newHead = new ListNode(cur.val);
            //将链表头的next指针指向已经反转好的链表
            newHead.next = pre;
            //更新已经反转好的链表头指针
            pre = newHead;
            //更新当前指针
            cur = cur.next;
        }
        return newHead;
    }
}