LeetCode 234. 回文链表

绝地灬酷狼 2021-09-27 00:18 287阅读 0赞

请判断一个链表是否为回文链表。

> 示例 1:  
> 输入: 1->2  
> 输出: false  
> 示例 2:  
> 输入: 1->2->2->1  
> 输出: true

解题思路：  
1.快慢指针找到中点  
2.将链表分为左右两个链表  
3.将右边的链表逆序  
4.对比左右链表是否相等（右边链表长度可能比左边链表少1 因此右边链表为空时结束循环）

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head==null||head.next==null)
                return true;
            ListNode p1 = head;
            ListNode p2 = head.next;
            while (p2!=null) {
                p2 = p2.next;
                if (p2 == null)
                    break;
                p2 = p2.next;
                p1 = p1.next;
            }
            //奇数，则p1指向中点
            //偶数，则p1指向左边的最后一个节点
            p2 = p1.next;
            p1.next = null;
            //p2逆序
            ListNode newHead = null;
            while(p2!=null){
                ListNode p = p2.next;//保存链表的next
                p2.next = newHead;//将head的next指向新的链表头
                newHead = p2;//将新链表头指向头结点
                p2 = p;//将head赋给之前保存的next
            }
            //head 为左边链表 newhead为右边链表
            while (newHead!=null){
                if(head.val!=newHead.val)
                    return false;
                head = head.next;
                newHead = newHead.next;
            }
            return true;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，287人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode234 回文链表

![20191203214400750.png][] 请判断一个链表是否为回文链表。示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1-

墨蓝/ 2023年06月19日 02:19/ 0 赞/ 107 阅读

相关 Leetcode.234. 回文链表

[234. 回文链表][234.] 请判断一个链表是否为回文链表。示例 1: 输入: 1->2 输出: false 示例 2: 输入:

古城微笑少年丶/ 2022年12月17日 08:42/ 0 赞/ 170 阅读

相关【LeetCode 234】回文链表

题目描述请判断一个链表是否为回文链表。示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1

今天药忘吃喽~/ 2022年11月28日 00:50/ 0 赞/ 158 阅读

相关 LeetCode234--回文链表

请判断一个链表是否为回文链表。进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？解法一： / Definition f

待我称王封你为后i/ 2022年11月17日 05:14/ 0 赞/ 169 阅读

相关 LeetCode 234. 回文链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

朴灿烈づ我的快乐病毒、/ 2022年11月01日 04:26/ 0 赞/ 205 阅读

相关 Leetcode 234. 回文链表

题目重述请判断一个链表是否为回文链表。示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: tr

你的名字/ 2022年09月01日 00:03/ 0 赞/ 179 阅读

相关 LeetCode234. 回文链表

请判断一个链表是否为回文链表。示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: tr

た入场券/ 2022年05月23日 03:48/ 0 赞/ 192 阅读

相关【LeetCode】234. 回文链表

题目链接：[https://leetcode-cn.com/problems/palindrome-linked-list/description/][https_leetco

痛定思痛。/ 2022年05月11日 11:22/ 0 赞/ 179 阅读

相关 LeetCode【234.回文链表】

题目描述 > 请判断一个链表是否为回文链表。示例 1 输入： 1 − > 2 1->2 1−>2 输出： f a l s e false false

r囧r小猫/ 2022年05月08日 12:18/ 0 赞/ 196 阅读

相关 LeetCode 234. 回文链表

请判断一个链表是否为回文链表。 > 示例 1: > 输入: 1->2 > 输出: false > 示例 2: > 输入: 1->2->2->1 > 输出:

绝地灬酷狼/ 2021年09月27日 00:18/ 0 赞/ 288 阅读