建设网站的网址,小游戏网站建设,server2012做网站,如何制作小程序下单描述
对于一个链表#xff0c;请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法#xff0c;判断其是否为回文结构。
给定一个链表的头指针A#xff0c;请返回一个bool值#xff0c;代表其是否为回文结构。保证链表长度小于等于900。
测试样例#xff1a; 1-…描述
对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。
给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。
测试样例 1-2-2-1 返回true 思路找到链表的中间节点偶数个的话取右边那个然后把从中间节点开始反转链表然后在用反转后的链表和反转的前半部分的链表比 反转链表和快慢指针 /*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
typedef struct ListNode LN;class PalindromeList {
public:LN* reverList(LN* head){if(headNULL){return head;}LN* n1,*n2,*n3;n1NULL;n2head;n3head-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3){n3n3-next;}}return n1;}LN* midNode(LN* head){LN* fast,* slow;fastslowhead;while(fast fast-next){slowslow-next;fastfast-next-next;}return slow;}bool chkPalindrome(ListNode* A) {// write code hereLN* midnodemidNode(A);LN* remidreverList(midnode);while(A remid){if(A-val !remid-val){return false;}AA-next;remidremid-next;}return true;}
};
