回文链表(详解)

LeetCode HOT 100回文链表

想完全理解这道题还请先转入反转单链表【图文详解】掌握反转链表的思想

问题描述:

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

思路方法解读:

当我们遇到回文问题会想到，在数组里面我们可以用两个指针一个从头一个从尾开始遍历到中间，进行比较，那对于链表的操作是复杂的，我们可不可以将链表的值复制在数组里，对数组进行操作？答案是可以的。我们可以将链表的值复制到新申请的数组当中，利用双指针在数组中进行判断，因为需要新的数组空间上有了开销，那么这种方法一定不是最好的。

给出代码:

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;
        while (head != nullptr) {
            vals.emplace_back(head->val);
            head = head->next;
        }
        for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) {
            if (vals[i] != vals[j]) {
                return false;
            }
        }
        return true;
    }
};
 

这种方法时间上需要遍历整个数组因此时间复杂度为O(n),空间上利用了辅助空间新数组因此也为O(n)。

如果想到了上面的方法，在面试时往往是不够的，我们需要考虑如果缩减他的时间或空间复杂度。时间上好像没有好的办法，我们都需要遍历链表，但是空间上我们想想如何不申请额外辅助空间，在原本链表上进行操作呢?

我们如果可以改变链表的部分指向，然后利用双指针进行比较呢?

力扣官方给出的思路是:

1. 找到前半部分链表的尾节点。
2. 反转后半部分链表。
3. 判断是否回文。
4. 恢复链表。
5. 返回结果。

使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

既然慢指针一次走一步，最终走到中间，那么我们是不是可以通过慢指针边走边反转前半部分链表呢?换言之思路就是:快指针走到末尾，慢指针刚好到中间。其中慢指针将前半部分反转。然后比较。

图解:

下方代码我做了详细的注解:

注意：if(fast!=nullptr)  
        {   
            slow=slow->next;
        }

这句if的意思是fast两种情况 一：链表长度n为奇数时，此时fast不为null，而是最后一个节 点，slow指向（（n-1）/2，从零开始的，正好是独立出来的那个节点，为了方便比较，需要移动slow指针到后半部分的起始位置） 二：链表长度n为偶数，此时fast为null，slow正好指向后半部分的起始位置， 所以不用移动 

对于上面图示，当奇数时slow走到3，但为了方便比较，需要将slow往后移动一个

class Solution {
public:
    bool isPalindrome(ListNode* head) {
    //快指针走到末尾，慢指针刚好到中间。其中慢指针将前半部分反转。然后比较。
        ListNode *slow=head,*fast=head,*cur=nullptr;
        //快慢指针,和cur用来反转链表
        while(fast!=nullptr&&fast->next!=nullptr)
        {
            //快慢指针一起走，快指针走两步，慢指针走一步
            //反转慢指针走的链表，当快指针走到末尾，慢指针就走到中间
            //其实就是反转前一部分链表
            fast=fast->next->next;
            ListNode *tmp=slow->next;
            slow->next=cur;//改变指向
            cur=slow;   
            slow=tmp;
        }
       //这句if的意思是fast两种情况 一：链表长度n为奇数时，此时fast不为null，而是最后一个节 点，slow指向（（n-1）/2，从零开始的，正好是独立出来的那个节点，为了方便比较，需要移动slow指针到后半部分的起始位置） 二：链表长度n为偶数，此时fast为null，slow正好指向后半部分的起始位置， 所以不用移动
        if(fast!=nullptr)  
        {   
            slow=slow->next;
        }
            //从中间往前 往后比较
            //slow继续往后 cur往前 此时前面链表已经反转
            while(slow!=nullptr)
            {
                if(slow->val!=cur->val)
                {
                    return false;
                }
                else if(slow->val==cur->val)
                {
                    slow=slow->next;
                    cur=cur->next;
                }
            }
            return true;
            //不考虑比较时复原链表 可以边比较边复原
   }
};

写的很仔细，对于每句代码我都有详细的解释，希望在理解时运行一句代码对着图理解，此外反转链表和双指针的思想务必掌握!

好了今天的分享就到这里，走过看过，点赞收藏是对我最大的回馈!有任何问题欢迎评论区留言，共同学习！

这里附上前几节关于链表题目的解析:

常见的链表面试问题详解(双指针思维)_

反转单链表【图文详解】

数据结构-单链表基本操作带图完整详解_