首页 > 代码库 > 每日编程-20170412
每日编程-20170412
题目描述
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。
测试样例:
1->2->2->1
返回:true
解答:
用栈即可,就是初次答链表,试一下
1 #include <stack> 2 using namespace std; 3 4 struct ListNode { 5 int val; 6 struct ListNode *next; 7 ListNode(int x) : val(x), next(NULL) {} 8 }; 9 10 class PalindromeList { 11 public: 12 bool chkPalindrome(ListNode* A) { 13 // write code here 14 bool answer = true; 15 ListNode *p = A; 16 stack<int> s; 17 while (p) 18 { 19 s.push(p->val); 20 p = p->next; 21 } 22 p = A; 23 while (p) 24 { 25 if (s.top()!= p->val) 26 { 27 answer = false; 28 break; 29 } 30 s.pop(); 31 p = p->next; 32 } 33 return answer; 34 } 35 };
每日编程-20170412
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。