面试金典题2.6
编写一个函数，检查输入的链表是否是回文的。
示例 1：
输入： 1->2 输出： false
示例 2：
输入： 1->2->2->1 输出： true
看到回文我直接想到的是reverse函数，但是我试了一下，好像怎么取巧都不行，有会的大佬评论区教教呗！！！感谢！！！！
然后我们还是用最常规的双指针的方法
leetcode代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> v;
while(head!=nullptr){
v.push_back(head->val);
head=head->next;
}
int i=0;
int j=v.size()-1;
while(i<j){
if(v[i]!=v[j]){
return false;
}
++i;
--j;
}
return true;
}
};思路其实不难理解，就是用数组将链表存下来，然后用双指针去比较就好了。当然也可以用递归的方法，但是这个题递归并没有节省空间复杂度，因此就不贴代码了。递归的思路就是定义一个指针，先让他到尾部，然后再同时从正向和逆向开始遍历。
原文地址：https://blog.csdn.net/m0_73096516/article/details/142438973
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！