当前位置：首页 > news >正文

回文链表力扣234

news 来源：原创 2025/6/9 8:39:16

思路:

对于这个题同样的找出题目的要求

1.判断回文

那么我们思考一下判断回文的方法，对于字符串我们只需要翻转一下就行，但是这不是通用的方法，在思考一下，我们是不是可以用双指针，一个在前一个在后，向中间靠拢，那么我们要如何实现在链表中。

首先我们要明确链表的遍历，只能从头到尾，也就是顺序遍历，也就是说要模拟双指针，那么就需要一个尾部指针，结合链表的遍历方式，我们可以设置一个头指针，指向头节点，在设置一个指针遍历到结尾。那么现在的问题是如何让尾指针向后移动，仔细思考一下什么东西可以向前走完以后还可以返回去，当然是递归了，所有大体的代码思路就有了。

1.建立一个指针遍历到尾部，建立一个指针指向头节点。

2.利用递归回溯判断回文。递归很抽象，建议大家多手动模拟简单的。

/*** 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) {}* };*/
class Solution {
public://建立函数判断是否回文ListNode *temp;bool sss(ListNode* tt){if(tt!=nullptr){//如果返回true代表到达最后需要开始判断回文了if(!sss(tt->next)){return false;}if(tt->val!==temp->val){//如果不相等那么一直返回会false。return false;}//头指针开始前移temp=temp->next;//开始判断回文}//到达链表最后了;return true;//向后返回}bool isPalindrome(ListNode* head) {temp=head;return sss(head);}
};

方法二

在链表上我们处理不了的话，如果这个是在数组里面是不是可以处理了呢，按着这个思路，将所有的数据存到数组里面就行了。(利用双指针开头讲了)

/*** 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) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {vector<int> v;ListNode *temp=head;while(temp!=nullptr){v.emplace_back(temp->val);temp=temp->next;}int i=0;int j=v.size()-1;while(i<=j){if(v[i]!=v[j]){return false;}i++;j--;}return true;}
};

扩展知识。

push_back与emplace_back区别（看不懂直接看总结）

`emplace_back` 和 `push_back` 都是 C++ 中 `std::vector` 的成员函数，用于向容器尾部添加元素，但它们在实现方式和性能上有显著区别：

1. 参数传递方式
`push_back`
接受一个已构造好的对象（拷贝或移动），然后将该对象添加到 `vector` 末尾。
std::vector<Foo> vec;
Foo obj(1, 2);
vec.push_back(obj); // 拷贝构造
vec.push_back(Foo(3, 4)); // 移动构造（如果 Foo 支持移动语义）

emplace_back
直接在 `vector` 的内存空间中构造对象，通过完美转发（perfect forwarding）传递参数给对象的构造函数，**避免临时对象的创建和拷贝/移动
vec.emplace_back(1, 2); // 直接调用 Foo(int, int) 构造函数

2. 性能差异
`push_back`
如果参数是临时对象（如右值），会触发移动构造（如果对象支持移动语义）；如果是左值，则触发拷贝构造。可能产生额外的拷贝/移动开销。

`emplace_back`
直接在容器内部构造对象，省去了临时对象的构造和拷贝/移动步骤，**通常更高效**（尤其是对复杂对象）。

类型要求
`push_back` 要求对象可拷贝或移动（如果使用右值引用）。
-`emplace_back` 无此要求，直接在容器内构造对象。 **4. 返回值（C++17 起）

`push_back` 无返回值。
-`emplace_back` 返回新插入元素的引用（C++17 新增）。

---*示例对比

#include <vector>
#include <string>

class Foo {
public:
Foo(int a, int b) { /* ... */ }
};

int main() {
std::vector<Foo> vec;

// 使用 push_back（需要构造临时对象）
vec.push_back(Foo(1, 2)); // 构造临时 Foo，再移动（或拷贝）到 vector

// 使用 emplace_back（直接在 vector 内构造）
vec.emplace_back(3, 4); // 直接调用 Foo(3, 4)，无临时对象
}

总结
-优先使用 `emplace_back`：避免不必要的拷贝/移动，提升性能。
- 谨慎使用 `push_back`：当需要显式拷贝或移动语义时，或兼容旧代码。

**注意
- 对于简单类型（如 `int`、`double`），两者性能差异可能忽略不计。
- 如果对象构造函数有 `explicit` 修饰，`emplace_back` 需注意参数匹配（与构造函数一致）。

push_back与emplace_back区别（看不懂直接看总结）

总结 -优先使用 `emplace_back`：避免不必要的拷贝/移动，提升性能。 - 谨慎使用 `push_back`：当需要显式拷贝或移动语义时，或兼容旧代码。

相关文章：

总结
-优先使用 `emplace_back`：避免不必要的拷贝/移动，提升性能。
- 谨慎使用 `push_back`：当需要显式拷贝或移动语义时，或兼容旧代码。