【牛客力扣习题笔记】链表的回文结构

作者：花生_TL007 | 2024-05-23 08:15:05

踩

牛客力扣

找中间结点（当为偶数时，有两个中间结点，取第二个）
利用快慢指针，slow指针走一步每次，fast指针每次走两步，快指针速度是慢指针的二倍。
如图：
在这里插入图片描述

逆置后半截链表（逆置后的新的头结点作为新的中间结点）
比如奇数个【1,2，3,2，1】从头结点和中间节点同时开始遍历，为空结束，如果都相等，说明是回文结构。
在这里插入图片描述

偶数个【1,2，2,1】
逆置后半截后，从头结点开始遍历到他的next为空时结束，中间结点同时开始遍历为空时结束，如果值都相等说明是回文结构。
在这里插入图片描述
因为这样遍历就可以只遍历一遍，保持时间复杂度是O(N）。

在这里插入图片描述

改变链表指针的指向，用三个指针变量分别标记。两个指针用来反转指向，第三个指针用来保存第三个结点，用于继续下一步改变指向。
接下来用第二种方法来解决。
（原来的头结点要指向NULL，head->next->head;)
在这里插入图片描述

while(next)
1

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/612053