​ leetcode 234. 回文链表 easy​

本文主要是介绍​ leetcode 234. 回文链表 easy​，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 leetcode 234. 回文链表 easy

题目描述：

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

解题思路：

快慢指针找到中间位置， 右半区逆序， 比较完之后再恢复回来

代码：

//
/*** 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 {
public:bool isPalindrome(ListNode* head) {if (!head || !head->next)return true;ListNode* slow = head, *fast = head;while (fast->next && fast->next->next){slow = slow->next;fast = fast->next->next;}ListNode *right = slow->next; // 右半区第一个节点ListNode *left_end = slow; // 保存左半区最后一个节点, 为了后面恢复回来.left_end->next = nullptr; // 断开左右半区right = reverse_list(right); // 反转右半区ListNode* cur_l = head, *cur_r = right;bool res = true;while (cur_l && cur_r){if (cur_l->val != cur_r->val){res = false;break;}cur_l = cur_l->next;cur_r = cur_r->next;}right = reverse_list(right); // 再次反转右半区 恢复回来left_end->next = right; // 连接左右半区return res;}ListNode* reverse_list(ListNode* head){ListNode *pre = nullptr, *cur = head, *back = nullptr;while(cur){back = cur->next;cur->next= pre;pre = cur;cur = back;}return pre;}};

---

这篇关于​ leetcode 234. 回文链表 easy​的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---