LeetCode—234.回文链表(Palindrome Linked List)——分析及代码（C++）数据结构与算法

LeetCode—234.回文链表[Palindrome Linked List]——分析及代码[C++]

一、题目
二、分析及代码

1. 原地翻转前半链表

（1）思路
（2）代码
（3）结果

2. 记录数值

（1）思路
（2）代码
（3）结果

三、其他

【LeetCode—234.回文链表(Palindrome Linked List)——分析及代码（C++）】
一、题目请判断一个链表是否为回文链表。
示例 1:

输入: 1->2 输出: false

示例 2:

输入: 1->2->2->1 输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、分析及代码 1. 原地翻转前半链表（1）思路
结合双指针法，快指针一次跳动2个节点，慢指针一次跳动1个节点，并翻转所跳过的部分。
则当快指针到达链表末尾时，慢指针到达中间节点，并已经翻转了前半链表。
原链表的前、后部分分成了对称的2个链表，依次比较即可。
（2）代码

class Solution { public: bool isPalindrome(ListNode* head) { if (head == NULL || head->next == NULL) return true; ListNode * fast = head->next; ListNode * slow = head; ListNode * succ = head->next; while (fast->next != NULL) { ListNode* pred = slow; fast = fast->next; slow = succ; succ = slow->next; //记录后继节点 slow->next = pred; //翻转前半链表 if (fast->next != NULL)//边界处理 fast = fast->next; else slow = pred; } head->next = NULL; //封闭原链表头部 while (succ != NULL) {//依次比较 if (slow->val != succ->val) return false; slow = slow->next; succ = succ->next; } return true; } };

（3）结果
执行用时：20 ms, 在所有 C++ 提交中击败了 93.92% 的用户；
内存消耗：12.4 MB, 在所有 C++ 提交中击败了 83.83% 的用户。
2. 记录数值（1）思路
遍历记录链表数值，并依次比较。
（2）代码

class Solution { public: bool isPalindrome(ListNode* head) { if (head == NULL || head->next == NULL) return true; vector nums; ListNode* node = head; while (node != NULL) { nums.push_back(node->val); node = node->next; } int size = nums.size(); int j = (size + 1) / 2, i = size / 2 - 1; while (j < size) if (nums[i--] != nums[j++]) return false; return true; } };

（3）结果
执行用时：24 ms, 在所有 C++ 提交中击败了 80.12% 的用户；
内存消耗：13.2 MB, 在所有 C++ 提交中击败了 23.57% 的用户。
三、其他暂无。