链表的回文结构
目录
一.题目及剖析
二.思路引入
三.代码引入
四.扩展
一.题目及剖析
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 herestruct 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)