一.题目及剖析
https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tab=note
众所周知,如果这道题的链表改为数组,这道题将十分简单,用左右指针就行,但人家说的是链表,显然左右指针是行不通的.
二.思路引入
1.找到链表的中间节点,将其分为两部分
2.将后半部分反转
3.如果反转后value与前半部分一样,则是回文结构
而前两步之前的我的博客有介绍
三.代码引入
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class PalindromeList { public: struct ListNode* intermediateNode(struct ListNode* head) { struct ListNode* slow, *fast; slow = fast = head; while(fast && fast->next) { fast = fast->next->next; slow = slow->next; } return slow; } struct ListNode* overturnList(struct ListNode* head) { struct ListNode *n1, *n2, *n3; n1 = NULL; n2 = n3 = head; if(head) n3 = head->next; while(n2) { n2->next = n1; n1 = n2; n2 = n3; if(n3) n3 = n3->next; } return n1; } bool chkPalindrome(ListNode* A) { // write code here struct ListNode* pcur = intermediateNode(A); struct ListNode* prev = overturnList(pcur); while(prev) { if(A->val != prev->val) return false; prev = prev->next; A = A->next; } return true; } };
四.扩展
当然对于这道题,我们还可以有其他的解法,比如遍历这个链表,将其中的value存放至一个数组中,然后我们就可以使用左右指针去解决,这个算法的时间复杂度是o(n+logn),而第一种方法的时间复杂度是o(n)
