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

1、题目介绍

2、解题思路

2.1、暴力破解法

2.2、快慢指针反转链表

1、题目介绍

原题链接： 234. 回文链表 - 力扣（leetcode）

示例 1：

示例 2：

提示：

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

2、解题思路

2.1、暴力破解法

一共为两个步骤：

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

/**
 * 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;
}

2.2、快慢指针反转链表

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

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

代码实现：

/**
 * 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;
}

更多【leetcode刷题】推荐：

【leetcode力扣】86. 分隔链表-csdn博客https://blog.csdn.net/zzzzzhxxx/article/details/133942678?spm=1001.2014.3001.5501 【leetcode力扣】297. 二叉树的序列化与反序列化-csdn博客https://blog.csdn.net/zzzzzhxxx/article/details/133827375 【leetcode力扣】lcr170 使用归并排序的思想解决逆序对问题（详细图解）_hacynn的博客-csdn博客https://blog.csdn.net/zzzzzhxxx/article/details/133578735