题解 | #判断一个链表是否为回文结构#
判断一个链表是否为回文结构
http://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
题意：
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
方法：
模拟
思路：重点：因为单向链表只能从前往后，所以要转换为数组这种可以双向（从前往后和从后往前）的数据结构。
首先，遍历链表存储到数组中；最后，遍历数组判断是否回文结构。
class Solution {
public:
int a[10000005]={0};
bool isPail(ListNode* head) {
ListNode* p=head;
int cnt=0;
while(p){//遍历链表存储到数组中
a[cnt++]=p->val;
p=p->next;
}
for(int i=0;i<cnt/2;i++){//遍历数组判断是否回文结构
if(a[i]!=a[cnt-i-1])
return false;
}
return true;
}
};
时间复杂度：%2Cn%E6%98%AF%E9%93%BE%E8%A1%A8%E9%95%BF%E5%BA%A6%EF%BC%8C%E9%81%8D%E5%8E%86%E9%93%BE%E8%A1%A8%E3%80%82)
空间复杂度：%2Cn%E6%98%AF%E9%93%BE%E8%A1%A8%E9%95%BF%E5%BA%A6%EF%BC%8C%E5%AD%98%E5%82%A8%E6%95%B0%E7%BB%84%E7%A9%BA%E9%97%B4%E3%80%82)
查看23道真题和解析
