题解 | #判断一个链表是否为回文结构#
判断一个链表是否为回文结构
http://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
思路是遍历所有结点,构造一个数组,并反转数组,然后顺序与链表结点比较,只比较一半即可判断是否是回文结构
// 注意:快指针一次走两步,慢指针一次走一步,可以实现寻找链表的中间结点 // 空间复杂度为1的思路是通过快慢指针找到中间结点,然后将中间结点以后的结点反转,然后分别从两条链的链首开始遍历,判断相等进而判断是否是回文串 // 下边方法空间复杂度为O(n) #include <bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int val): val(val), next(nullptr) {}; }; class Solution { public: /** * * @param head ListNode类 the head * @return bool布尔型 */ bool isPail(ListNode* head) { // write code here // 判断链表是否是回文结构 // 只能使用头插法复制一份逆转后的链表,然后使用双指针法比较一半的链表? if (!head) return true; vector<int> rvec; ListNode *cur = head; while (cur) { rvec.push_back(cur->val); cur = cur->next; } reverse(rvec.begin(), rvec.end()); cur = head; for (int i = 0; i < rvec.size()/2; i++, cur = cur->next) { if (cur->val != rvec[i]) return false; } return true; } };