首页 > 代码库 > 链表的回文结构
链表的回文结构
时间限制:3秒 空间限制:32768K 热度指数:7637
本题知识点: 链表 栈
题目描述
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。
测试样例:
1->2->2->1
返回:true
1 /* 2 struct ListNode { 3 int val; 4 struct ListNode *next; 5 ListNode(int x) : val(x), next(NULL) {} 6 };*/ 7 class PalindromeList { 8 public: 9 bool chkPalindrome(ListNode* A) { 10 // write code here 11 if(A==NULL) 12 return true; 13 ListNode* slow; 14 ListNode* fast; 15 ListNode* temp; 16 17 slow=A; 18 fast=A; 19 20 while(fast->next!=NULL) 21 { 22 temp=slow; //temp用来存放最后mid之前的一个元素 23 slow=slow->next; 24 fast=fast->next; 25 if(fast->next!=NULL) 26 fast=fast->next; 27 } 28 if(mid==A) 29 return true; //链表元素个数为1时; 30 ListNode* cur; 31 32 temp->next=NULL; 33 cur=slow->next; 34 slow->next=NULL; 35 36 while(cur!=NULL) 37 { 38 temp=cur->next; 39 cur->next=slow; 40 slow=cur; 41 cur=temp; 42 } 43 44 while(A!=NULL && slow!=NULL) 45 { 46 if(A->val==slow->val) 47 { 48 A=A->next; 49 slow=slow->next; 50 } 51 else 52 return false; 53 } 54 return true; 55 56 } 57 };
链表的回文结构
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。