题解 | #判断一个链表是否为回文结构#
判断一个链表是否为回文结构
http://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
思路： 两次正序遍历解决。
1. 第一次把每个节点值按顺序依次放到 vector<int > v1 里面，这个是正向顺序，同时得到总节点数 n.
2. 第二次遍历时候，正数第 t 个节点就是逆序的 第 n-t 个节点。 所以第二遍从 v2 尾部开始依次赋值就好了。 v2 里面存的就是 逆序遍历结果。
特点：
1.O（N）复杂度
2. 不改变原链表结构
class Solution {
public:
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
bool isPail(ListNode* head) {
// write code here
if (!head || !head->next) {
return true;
}
std::vector <int> v1;
ListNode* p = head;
int i = 0;
while (p) {
v1.push_back(p->val);
p = p->next;
i++;
}
int n = i;
vector<int> v2(n, 0);
ListNode *q = head;
i--;
while (q) {
v2[i] = q->val;
q = q->next;
i--;
}
for (int j = 0; j<n; ++j) {
if (v1[j] != v2[j]) {
return false;
}
}
return true;
}
};
投递拼多多集团-PDD等公司10个岗位 >
查看15道真题和解析