今天聊点有意思的,昨天写了一个链表翻转,说一说里面大家会遇到的坑,具体可以看 教你三指针拿捏链表翻转-CSDN博客
有这样一个场景,给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
示例 1:
输入:head = [1,2,2,1]
输出:true
在看完链表翻转后,其实就有一个思路,我们把原来的链表翻转过来,然后遍历两个链表的值是否相等不就行了吗?
好,链表翻转在上一篇种已经有了,我们只需要在遍历链表就行。
代码如下:
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* pre = nullptr;ListNode* cur = head;while(cur != nullptr) {ListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;}bool isPalindrome(ListNode* head) {ListNode* res = reverseList(head);while(head != nullptr) {if(res->val != head->val) return false;res = res->next;head = head->next;}return true;}
};
这样的做法是否正确呢?前面氛围已经铺垫好了,前面分析其实有一个漏洞,大家也可以仔细分析一下。链表翻转是没问题的,把链表从左到右的变成从右到左的然后在遍历也是没问题的,但是想一下,当我们正序遍历原链表的时候,原链表生态已经被破坏了,换句话说就是,翻转后的链表是从右至左,此时head开始正序遍历,他已经不是原来那个链表了。
所以这么做,正序遍历链表的时候就会读到空指针,出现奇奇怪怪的bug。