首页 > 代码库 > 链表回文判断（C++）
链表回文判断（C++）
题目描述：
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true
思路：
由于空间复杂度要求为O(1)，也就是说临时占用空间和输入数据规模无关，因此无法利用数组或者是栈进行判断。因此先找到中间位置将后半部分指针翻转，然后两端分别比较。注意这种方法会修改原链表，但是空间复杂度要求为O(1)也只能这么做了。
程序运行流程：
1、利用快慢指针找到中间的位置（起初均指向头结点，然后pSlow一次走一步，pFast一次走两步。注意不需要区分链表结点个数是奇数还是偶数）；
2、将后半部分指针翻转；
3、最后再进行一次遍历，一个从前向后，一个从后向前。
下图是演示图（分为链表结点个数奇数和偶数两种情况），当pFast或pFast->next到达尾部（为NULL）时，pSlow正好到达中间位置。其中当链表结点个数为偶数时，pFast首先变为NULL；当链表结点个数为奇数时，pFast->next首先变为NULL。
代码：
1 /* 2 本程序说明： 3 4 时间限制：3秒 空间限制：32768K 热度指数：8332 5 本题知识点： 链表 栈 6 7 题目描述 8 对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。 9 给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。 10 测试样例： 11 1->2->2->1 12 返回：true 13 14 */ 15 16 #include <iostream> 17 using namespace std; 18 19 struct ListNode { 20 int val; 21 struct ListNode *next; 22 ListNode(int x) : val(x), next(NULL) {} 23 }; 24 25 //链表结点构造 26 ListNode* create_list_node(int val) 27 { 28 ListNode* pNode = new ListNode(val); 29 return pNode; 30 } 31 //链表结点连接 32 void connect_list_node(ListNode* pCur, ListNode* pNext) 33 { 34 pCur->next = pNext; 35 } 36 37 38 39 class PalindromeList { 40 public: 41 bool chkPalindrome(ListNode* A) { 42 // write code here 43 ListNode* pSlow = A; 44 ListNode* pFast = A; 45 46 while(pFast != NULL && pFast->next != NULL) 47 { 48 pSlow = pSlow->next; 49 pFast = pFast->next->next; 50 } 51 //反转链表后半部分指针 52 ListNode* prev = pSlow;//临时保存用 53 pSlow = pSlow->next; 54 while(pSlow != NULL) 55 { 56 ListNode* tmp = pSlow->next;//保存后面的结点 57 pSlow->next=prev; 58 prev = pSlow; 59 pSlow = tmp; 60 } 61 62 ListNode* pForward = A;//指向头结点 63 ListNode* pBackward= prev;//指向链表最后一个结点 64 65 while(!(pForward == pBackward || pForward->next == pBackward)) 66 { 67 if(pForward->val != pBackward->val) 68 return false; 69 pForward = pForward->next; 70 pBackward = pBackward->next; 71 } 72 return true; 73 } 74 }; 75 76 void test() 77 { 78 //创建结点 79 ListNode* pNode1 = create_list_node(1); 80 ListNode* pNode2 = create_list_node(7); 81 ListNode* pNode3 = create_list_node(2); 82 ListNode* pNode4 = create_list_node(2); 83 ListNode* pNode5 = create_list_node(7); 84 ListNode* pNode6 = create_list_node(1); 85 // ListNode* pNode7 = create_list_node(13); 86 // ListNode* pNode8 = create_list_node(45); 87 // ListNode* pNode9 = create_list_node(-7); 88 89 //连接结点 90 connect_list_node(pNode1,pNode2); 91 connect_list_node(pNode2,pNode3); 92 connect_list_node(pNode3,pNode4); 93 connect_list_node(pNode4,pNode5); 94 connect_list_node(pNode5,pNode6); 95 // connect_list_node(pNode6,pNode7); 96 // connect_list_node(pNode7,pNode8); 97 // connect_list_node(pNode8,pNode9); 98 99 PalindromeList test;100 101 bool flag=test.chkPalindrome(pNode1);102 cout<<flag<<endl;103 104 }105 106 int main()107 {108 test();109 return 0;110 }
欢迎交流。
链表回文判断（C++）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。