【LeetCode力扣】234 快慢指针 | 反转链表 | 还原链表

小灰灰 2024-03-27 19:22 4阅读 0赞

![81f7161ae36c4d6a972ae6c244506c5a.png][]

**目录**

1、题目介绍

2、解题思路

2.1、暴力破解法

2.2、快慢指针反转链表

![429a1a01dbb3453695ac8f73b4a93198.gif][]

## 1、题目介绍 ##

**原题链接：** [234. 回文链表 - 力扣（LeetCode）][234. _ - _LeetCode]

![47d853c0af714074b29250fcbace5d8d.png][]

**示例 1：**

![c101b584e41a4431b02527bf9c1b4425.png][]

> **输入：**head = \[1,2,2,1\]  
> **输出：**true

**示例 2：**

![684824eaa2584c4dad96d741491973fc.png][]

> **输入：**head = \[1,2\]  
> **输出：**false

**提示：**

>  *  链表中节点数目在范围\[1, 10^5\] 内
>  *  0 <= Node.val <= 9

**进阶：**你能否用 `O(n)` 时间复杂度和 `O(1)` 空间复杂度解决此题？

## 2、解题思路 ##

> 判断回文，就是判断是否是对称的。有些朋友对于数组的回文判断非常熟悉，但是对链表的回文判断可能就无从下手了，其实都一样的。有一种非常简单的方式就是**将链表转化成数组**，然后就是判断该数组是否回文就可以了，这种方式统称暴力破解法，简单粗暴。下面就来先带着大家看一下这道题的**暴力破解法**。

### 2.1、暴力破解法 ###

一共为两个步骤：

1.  复制链表值到数组列表中。
2.  使用双指针法判断是否为回文。

> 首先按照题目要求的最大大小定义一个大小为100001的整型数组，接着通过循环遍历将链表中每个结点的值取出放入数组中，最后通过两个指针，一个从左一个从右分别判断是否相等，只要遇到一个不相等就返回false，否则当循环结束时返回true。

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    bool isPalindrome(struct ListNode* head){
        int arr[100001] = {0},num = 0;
        while(head)
        {
            arr[num] = head->val;
            head = head->next;
            num++;
        }
        int i= 0;
        int j =0;
        for(i = 0,j = num-1; i<j; i++,j--)
        {
            if(arr[i]!=arr[j])
            {
                return false;
            }
        }
        return true;
    }

> 时间复杂度：**O(n)**，其中 n 指的是链表的元素个数。
> 
>  *  第一步：遍历链表并将值复制到数组中，O(n)。
>  *  第二步：双指针判断是否为回文，执行了 O(n/2) 次的判断，即O(n)。
>  *  总的时间复杂度：O(2n)=O(n)。
> 
> 空间复杂度：**O(n)**，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。

> **进阶：**你能否用 `O(n)` 时间复杂度和 `O(1)` 空间复杂度解决此题？
> 
> 下面带大家做一下本题的进阶，使用**快慢指针反转链表**实现空间复杂度为O(1)的算法。

### 2.2、快慢指针反转链表 ###

整个流程可以分为以下五个步骤：

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

> 对于第一步找到前半部分链表的尾结点，我们可以计算链表结点个数然后再找到前半部分的尾结点，也可以通过**快慢指针**一次遍历找到前半部分的尾结点。
> 
> **慢指针一次走一步，快指针一次走两步，**快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

![43a648a984384139bb0abbe5a281963d.png][]

![e20dc6b3521d4ddf89a2087f33538127.png][]

![31cd72eda5204f57997f1b23ca15a8f1.png][]

> 此时slow就是前半部分的尾结点，而slow的下一个结点就是后半部分的头结点。于是让fast回到slow的next结点处，将后半部分的结点全部反转，然后slow即前半部分的尾结点置空。

![f31ad2fd325e4d7ea12046eb260520f1.png][]

> 紧接着将让slow从head重新出发，fast从最后结点出发，分别向中间结点靠近并判断，只要相等就一直向中间靠近，遇到不相同时直接返回false，否则当循环退出时返回true。

![0dd1e05c54844d25b43a3de3f27967fc.png][]

![cf93edb7bab04bd286a8d53049f19a3e.png][]

![ea7a8627e65f4fdb9f03f46d6f540c71.png][]

![b3b18053c48e46deae47bc9128656b90.png][]

> 最后在将反转链表还原回去即可。

**代码实现：**

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    bool isPalindrome(struct ListNode* head){
        if(head == NULL || head->next == NULL)
        {
            return true;
        }
        struct ListNode* n1 = head;
        struct ListNode* n2 = head;
        //快慢指针遍历
        while(n2->next != NULL && n2->next->next != NULL)
        {
            n1 = n1->next;          //慢指针
            n2 = n2->next->next;    //快指针 
        }
        n2 = n1->next;   //右边第一个
        n1->next = NULL;
        struct ListNode* n3;
        //反转右半边链表
        while(n2 != NULL)
        {
            n3 = n2->next;  //n3存放n2的next
            n2->next = n1;
            n1 = n2;
            n2 = n3;
        }
        //当循环结束时n1所指向的位置就是链表最后一个结点，
        n2 = n3 = n1;  //将n2和n3指回最后一个节点
        n1 = head;     //n1回到头结点
        bool flag = true;
        //判断是否是回文
        while(n1 != NULL && n2 != NULL)
        {
            if(n1->val != n2->val)
            {
                flag = false;
                break;
            }
            n1 = n1->next;
            n2 = n2->next;
        }
        //还原链表
        n2 = n3->next;    //n3此时指向最后一个结点，因为反转了链表，n3的next就是上一个结点
        n3->next = NULL;
        while(n2!=NULL)
        {
            n1 = n2->next;
            n2->next = n3;
            n3 = n2;
            n2 = n1;
        }
    
        return flag;
    }

> 时间复杂度：**O(n)**，其中 n 指的是链表的大小。
> 
> 空间复杂度：**O(1)**。我们只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)。

更多【LeetCode刷题】 推荐：

[【LeetCode力扣】86. 分隔链表-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://blog.csdn.net/zzzzzhxxx/article/details/133942678?spm=1001.2014.3001.5501][LeetCode_86. _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133942678_spm_1001.2014.3001.5501][【LeetCode力扣】297. 二叉树的序列化与反序列化-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://blog.csdn.net/zzzzzhxxx/article/details/133827375][LeetCode_297. _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133827375][【LeetCode力扣】LCR170 使用归并排序的思想解决逆序对问题（详细图解）\_Hacynn的博客-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/c5cba103189c4bd5b0e8f207c1ff9498.png][LeetCode_LCR170 _Hacynn_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133578735]

![c5b85edf8ec44b6d84e2e70fab38896e.gif][]

**如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！**

[81f7161ae36c4d6a972ae6c244506c5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/428b35e8d01b4426a4882ea990155daa.png
[429a1a01dbb3453695ac8f73b4a93198.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/dea01bb8a84c4e08b2736f31e2e54a7f.png
[234. _ - _LeetCode]: https://leetcode.cn/problems/palindrome-linked-list/submissions/471376614/?envType=list&envId=ixRuNo8f
[47d853c0af714074b29250fcbace5d8d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/f6b34d42b998407998286bc85c1d3389.png
[c101b584e41a4431b02527bf9c1b4425.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/76b94358ad4a4b0cb40099e879e5350b.png
[684824eaa2584c4dad96d741491973fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/5df3bcff2a20469c904cc50bb869524a.png
[43a648a984384139bb0abbe5a281963d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/b23bb44513244227b04affb1e19c0998.png
[e20dc6b3521d4ddf89a2087f33538127.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/9c92835de1aa4d13807c9156f26f6808.png
[31cd72eda5204f57997f1b23ca15a8f1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/c9241ebaae6c4000a20fc53c06a35e0a.png
[f31ad2fd325e4d7ea12046eb260520f1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/b8933b19b1044aa492f8ef3435bbd871.png
[0dd1e05c54844d25b43a3de3f27967fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/cdad6073a9d64338a9e0849499f5cb2b.png
[cf93edb7bab04bd286a8d53049f19a3e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/520336befae6412b81b210ba06c8f0f4.png
[ea7a8627e65f4fdb9f03f46d6f540c71.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/aca8b3ee0ed5486a8cc9352082919587.png
[b3b18053c48e46deae47bc9128656b90.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/72cdd1d9fdba4cb1b16c11585026835f.png
[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[LeetCode_86. _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133942678_spm_1001.2014.3001.5501]: https://blog.csdn.net/zzzzzhxxx/article/details/133942678?spm=1001.2014.3001.5501
[LeetCode_297. _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133827375]: https://blog.csdn.net/zzzzzhxxx/article/details/133827375
[LeetCode_LCR170 _Hacynn_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133578735]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/c5cba103189c4bd5b0e8f207c1ff9498.png
[c5b85edf8ec44b6d84e2e70fab38896e.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/6d8a248b73a94f3aa2c82f1e8b93bb14.png