射阳建设网站,深圳华强北招聘网,app推广服务部,南宁百度网站公司电话归纳编程学习的感悟#xff0c; 记录奋斗路上的点滴#xff0c; 希望能帮到一样刻苦的你#xff01; 如有不足欢迎指正#xff01; 共同学习交流#xff01; #x1f30e;欢迎各位→点赞 #x1f44d; 收藏⭐ 留言#x1f4dd;抱怨深处黑暗#xff0c;不如提灯前行…
归纳编程学习的感悟 记录奋斗路上的点滴 希望能帮到一样刻苦的你 如有不足欢迎指正 共同学习交流 欢迎各位→点赞 收藏⭐ 留言抱怨深处黑暗不如提灯前行 题目描述
给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。 示例 1 输入head [1,2,2,1]
输出true示例 2 输入head [1,2]
输出false提示
链表中节点数目在范围[1, 105] 内0 Node.val 9
思路推导
判断该链表是否为回文链表数据范围node.val9,节点数量∈[1,10^5]node.val 9, 节点数量 ∈ [1,10^5]node.val9,节点数量∈[1,10^5 ]
可选方案1转数字判断是否为回文数 可选方案2转字符串判断是否为回文串 但这样做就没有利用到链表自身的性质因此不是最合适的解法。 根据「206.反转链表」的思路可以在完成「链表前半部分的反转」之后通过双指针指向前半部分的头结点和后半部分链表的头结点每次推进一步并判断数值是否相等。 但这存在「奇数节点个数的链表」和「偶数节点个数的链表」的前半部分和后半部分划分上的不同的问题。 情况分析 回文链表必然会存在「奇数个节点」的链表和「偶数个节点」的链表。
对于长度为奇数的回文链表 1-2-3-2-1长度为5的链表那么从回文中心3向左右两侧出发会遍历得到相同的数字序列。 对于偶数长度的回文链表 1-2-2-1长度为4的链表如果回文那么从第2和第3个节点出发向两侧扫描可以得到相同的数字序列。 因此假设节点个数为n
奇数链表
回文中心为(n1)/2个节点 回文边界为(n1)/2 - 1(n1)/2 1 偶数链表
没有回文中心 回文边界n/2和n/2 1 之后可以通过「统计节点个数」-「对奇偶链表需要翻转的节点个数分别判断完成前半部分反转」-「从前半部分链表和后半部分链表的头结点向两侧扫描推进判断数字是否相同」的方法来判断回文链表。
但目前这样的考虑过于复杂了因为实际上我们无需计算节点个数只需要确定链表中间节点的位置即可。「确定链表中间节点的位置」的方法通常使用快慢指针法。
示例分析 设计双指针slow head, fast head 「奇数链表」和「偶数链表」最终确定的中间节点不一致我们可以先确定「链表中间节点位置」再「反转前半部分的链表」也可以考虑在slow指针推进过程中完成「局部反转」这样到达「中间位置节点」时恰好完成了前半部分的反转。
偶数链表的示例分析
局部翻转还需要的变量pre以及变量初始化
设计pre null, slow fast head;
当前循环条件未知。
每次循环slow指针每次前进一步就翻转局部链表fast指针前进两步。
偶数节点情况
初始化
null 1 - 2 - 2 - 1 - null^ ^
pre slow,fast
---------------------------------
第1轮循环
null- 1 2 - 2 - 1 - null^ ^ ^pre slow fast
---------------------------------
第2轮循环
null- 1 - 2 2- 1- null^ ^ ^pre slow fast
第二次循环结束后就已经完成了前半部分链表的反转
pre指向前半部分链表的第一个元素。
slow到达「中间节点的第二个节点」。
slow指针指向后半部分链表的第一个元素。
偶数链表的循环退出条件是 fast null
奇数链表的示例分析 奇数链表模拟
初始化
null 1 - 2 - 3 - 2 - 1 - null^ ^
pre slow,fast
第一轮循环
null- 1 2 - 3 - 2 - 1 - null^ ^ ^pre slow fast第二轮循环
null- 1 - 2 3 - 2 - 1 - null^ ^ ^pre slow fast
第二轮循环结束后slow到达「链表中间节点」位置。
循环退出条件是 fast.next null
循环退出时
fast 链表最后一个元素
pre 指向前部分链表的第一个元素
slow 指针指向后部分链表的第一个元素。
需要特殊处理即将slow指针向后推进一位
以保证和「偶数链表」相同slow指针指向后半部分回文链表的第一个元素。抽取循环结束时的共性
pre指向前半部分链表的第一个元素。 slow指针经过处理后指向后半部分链表的首个元素 循环退出条件 对于奇数链表为fast.next null 对于偶数链表为fastnull
通过「奇数链表」和「偶数链表」的示例分析得到伪代码 循环开始
1. 变量初始化
双指针赋值slow head, fast head,
局部旋转前一个变量指针pre null
局部翻转需要保存的下一个节点 tmp null
2. 双指针推进循环
循环条件(fast ! null fast.next ! null){2.1 快指针每次推进两步。2.2 慢指针通过「局部反转」的方式进行指针的推进。
}
3.循环结束后的情况分析3.1 偶数链表循环结束后fast nullpre指向前半部分第一个回文数slow指向后半部分第一个回文数3.2 奇数链表循环结束后fast !null, fast.next nullpre指向前半部分第一个回文数slow指向后半部分第一个节点链表中间节点。为使得一致slow指针需要指向第一个回文数需要将slow向前推进一步
因此如果fast ! null将slow指针推进一步。
4. 此时pre指向前半部分链表第一个回文数slow指向后半部分链表第一个回文数。
循环判断
循环条件pre! null || slow.next ! null
向两边同时推进pre和slow比较pre.val和slow.val是否相等
如果pre.val ! slow.val说明不是回文数返回false。
当pre和slow都推进到链表末尾说明每个数都相等返回true。代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode LNode;
bool isPalindrome(struct ListNode* head) {LNode*fast;LNode*slow;fasthead;slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;}LNode *temp,*pre,*cur;preNULL;curslow;while(cur){tempcur-next;cur-nextpre;precur;curtemp;}LNode*p;phead;while(prep){if(p-val!pre-val){break;}pp-next;prepre-next;}if(pNULL||preNULL){return true;}else{return false;}
} 复杂度分析
时间复杂度O(n)双指针扫描链表一遍O(n)局部反转时间复杂度O(1)回文数比较时间复杂度O(n)。 空间复杂度O(1)指针只占用了常量的空间。
