【链表】LC 234.回文链表

文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析考虑空间复杂度双指针解法空间复杂度O(1)、时间复杂度O(n)不考虑空间复杂度复制到数组双指针空间复杂度O(n)、时间复杂度O(n)2、解题代码考虑空间复杂度双指针解法空间复杂度O(1)、时间复杂度O(n)不考虑空间复杂度复制到数组双指针空间复杂度O(n)、时间复杂度O(n)三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接234.回文链表2、题目描述二、个人思路整理1、思路分析考虑空间复杂度双指针解法空间复杂度O(1)、时间复杂度O(n)利用快慢指针寻找链表中点快、慢指针同时从头开始遍历链表快指针每次走两步慢指针每次走一步当快指针走到末尾、慢指针指向的是链表中点反转慢指针指向的后半段链表将前半段链表与反转后的逐元素比较均相等则回文链表否则非回文。可选若希望不改变原链表结构可以在判断完之后再重新反转一次后半段链表恢复原结构但要注意在前面代码中需要保存反转后的后半段链表的头节点方便反转回来同时注意在回文或非回文状态下均要能恢复就不能像下面代码一样判断完直接返回结果而是设置一个flag记录结果最后再恢复完结构后再返回flag不考虑空间复杂度复制到数组双指针空间复杂度O(n)、时间复杂度O(n)将链表元素依次复制数组中然后数组头、尾各设置一个指针依次从前、从后向数组中部移动直到相遇同时在移动过程中依次比较指向元素的值如果都等则回文如果存在不相等元素则非回文。2、解题代码考虑空间复杂度双指针解法空间复杂度O(1)、时间复杂度O(n)/** * 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) {} * }; */classSolution{public:boolisPalindrome(ListNode*head){ListNode*slowhead;ListNode*fasthead;//注意:fast-next ! nullptr这个条件不能丢因为后续要访问fast-next-next需要保证fast-next非空否则会导致空指针异常while(fast!nullptrfast-next!nullptr){fastfast-next-next;slowslow-next;}ListNode*p1head;ListNode*p2reverseList(slow);//反转后半段链表//前半段链表与后半段链表逐个比较若存在不相等元素则非回文链表while(p1!nullptrp2!nullptr){if(p1-val!p2-val){returnfalse;}p1p1-next;p2p2-next;}returntrue;}private:ListNode*reverseList(ListNode*head){//需要返回反转后链表的头节点不能为无返回值ListNode*prenullptr;// 初始应该为nullptr,作为新链表的结尾ListNode*curhead;while(cur!nullptr){ListNode*nextTempcur-next;//1. 先保存下一个需要改变指针执行的节点cur-nextpre;//2. 反转当前节点的指针precur;//3. pre前进一步curnextTemp;//4. cur前进一步}returnpre;}};不考虑空间复杂度复制到数组双指针空间复杂度O(n)、时间复杂度O(n)/** * 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) {} * }; */classSolution{public:boolisPalindrome(ListNode*head){vectorintv;//注意是值不要写成LinkNode*类型的数组ListNode*tmphead;while(tmp!nullptr){v.push_back(tmp-val);tmptmp-next;}coutv.size();for(inti0,jv.size()-1;iv.size()/2;i,j--){coutiendl;coutjendl;if(v[i]!v[j]){returnfalse;}}returntrue;}};三、知识风暴vector中的push_back()与emplace_back()push_back()复制/移动构造需创建临时对象然后将其复制Copy或移动Move到vector管理的内存空间中适合插入一个已经创建好的变量emplace_back()原位构造不创建临时对象直接在vector末尾的内存区域调用元素的构造函数适合在容器末尾现场构造一个复杂对象。