面试金典题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;}
};
思路其实不难理解,就是用数组将链表存下来,然后用双指针去比较就好了。当然也可以用递归的方法,但是这个题递归并没有节省空间复杂度,因此就不贴代码了。递归的思路就是定义一个指针,先让他到尾部,然后再同时从正向和逆向开始遍历。