html网站的上传,招商加盟代运营公司,中建名城建设有限公司 网站,淘客软件自动做网站题目描述#xff1a;链表的回文结构_牛客题霸_牛客网 (nowcoder.com) 对于一个链表#xff0c;请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法#xff0c;判断其是否为回文结构。 给定一个链表的头指针A#xff0c;请返回一个bool值#xff0c;代表其是否为回文结…题目描述链表的回文结构_牛客题霸_牛客网 (nowcoder.com) 对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。 给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900 测试样例
1-2-2-1 返回true
题解思路 找到中间节点在利用翻转链表的方法将以中间节点newList为新的头节点来翻转链表通过遍历比较两个链表的各个值如果对应有一个节点的数值不相等就返回false如果所以节点的数值都相等就返回ture。 代码
struct ListNode* midNode(ListNode* head)
{struct ListNode* fast head, *slow head;while(fast fast-next){fast fast-next-next;slow slow-next;}return slow;
}struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* n1 NULL, *n2 head, *n3 head-next;while(n2 ! NULL){n2-next n1;n1 n2;n2 n3;if(n3 ! NULL){n3 n3-next;}}return n1;
}
bool chkPalindrome(ListNode* A) {// 找到中间节点struct ListNode* mid midNode(A);// 翻转链表struct ListNode* newHead reverseList(mid);// 比较struct ListNode* cur1 A, *cur2 newHead;while(cur1 cur2){if(cur1-val ! cur2-val){return false;}else {cur1 cur1-next;cur2 cur2-next;}}return true;} 注
如果你还想知道回文数是如何判断的可以看一下这一篇博客http://t.csdn.cn/giq9u
翻转链表方法详细解释http://t.csdn.cn/BLwnA
找链表中间节点http://t.csdn.cn/uYTNe 本次内容到此结束了如果你觉得这篇博客对你有帮助的话 希望你能够给我点个赞鼓励一下我。感谢感谢……
