【LeetCode刷题笔记】LCR.27 回文链表

创作不易，本篇文章如果帮助到了你，还请点赞关注支持一下♡>𖥦<)!!
主页专栏有更多知识，如有疑问欢迎大家指正讨论，共同进步！
更多算法知识专栏：算法分析🔥
给大家跳段街舞感谢支持！ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ

在这里插入图片描述
LeetCode题解专栏：【LeetCode刷题笔记】

题目链接

LCR 027. 回文链表 - 力扣（LeetCode）

一、题目描述

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

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

二、示例

示例 1：

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

示例 2：

在这里插入图片描述

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

三、题目分析

判断回文链表：

先获取链表长度

在链表的中间位置断开，分为前后两个链表

通过两个指针指向两条链表的头节点，遍历两条链表不断进行判断，如果有不同的节点就不是回文链表

两条链表都遍历完毕即为回文链表

四、代码实现（C++）

Definition for singly-linked list.struct ListNode {int val;ListNode next;ListNode()  val(0), next(nullptr) {}ListNode(int x)  val(x), next(nullptr) {}ListNode(int x, ListNode next)  val(x), next(next) {}};class Solution {
publicint getLen(ListNode head){if(head == nullptr) return 0;int len = 0;ListNode temp = head;while(temp){len++;temp = temp-next;}return len;}bool isPalindrome(ListNode head) {if(head == nullptr) return false;int len = getLen(head);ListNode slow = head;ListNode fast = head;for(int i=0;ilen2;i++){fast = fast-next;}反转后半段链表ListNode backHead = reverse(fast);while(slow && backHead){if(slow-val!=backHead-val){return false;}slow = slow-next;backHead = backHead-next;}return true;}ListNode reverse(ListNode head){ListNode p1 = nullptr;ListNode p2 = head;while(p2){ListNode p3 = p2-next;p2-next = p1;p1 = p2;p2 = p3;}return p1;}
};