给你一个单链表的头节点head请你判断该链表是否为回文链表。如果是返回true否则返回false。示例 1输入head [1,2,2,1]输出true示例 2输入head [1,2]输出false提示链表中节点数目在范围[1, 105]内0 Node.val 9进阶你能否用O(n)时间复杂度和O(1)空间复杂度解决此题给你一个单链表的头节点head请你判断该链表是否为回文链表。如果是返回true否则返回false。示例 1输入head [1,2,2,1]输出true示例 2输入head [1,2]输出false提示链表中节点数目在范围[1, 105]内0 Node.val 9进阶你能否用O(n)时间复杂度和O(1)空间复杂度解决此题思路1将链表的数填充到数组中然后用双指针判断回文bool isPalindrome(ListNode* head) { if(!head) return false; vectorint res; ListNode* pMovehead; while(pMove){ res.push_back(pMove-val); pMovepMove-next; } int sizeres.size(); int left0,rightsize-1; while(rightleft){ if(res[left]!res[right--]) return false; } return true; }思路2递归链表1、定义一个全局的链表节点指针指向头节点pMove2、递归链表先让头节点指针frontNode走到尾节点3、尾节点pMove和frontNode对比假如不相等直接返回false4、如果有一个节点返回false全部节点都返回false5、如果返回true进入下一层继续比较直到比较全部节点返回trueclass Solution { public: ListNode* pMove; bool dromeCycle(ListNode* tail){ if(!tail) return true; bool retdromeCycle(tail-next); if(!ret) return false; else{ if(pMove-val!tail-val) return false; pMovepMove-next; } return true; } bool isPalindrome(ListNode* head) { if(!head) return false; pMovehead; return dromeCycle(head); } };推荐一个零声教育学习教程个人觉得老师讲得不错分享给大家[LinuxNginxZeroMQMySQLRedisfastdfsMongoDBZK流媒体CDNP2PK8SDockerTCP/IP协程DPDK等技术内容点击立即学习:链接