每日一题——回文链表

简介: 每日一题——回文链表

回文链表

题目链接

回文结构即字符串正序逆序完全一致,如“1 2 3 4 3 2 1”,那么我们就要想办法同时比较链表头和链表尾的元素,看其是否相等。

下面介绍一种最常用的方法:


思路

如果我们仔细观察回文结构,就会得到一个结论:

将一个回文结构从正中间分隔,再将后半部分逆序,那么前半部分就一定等于后半部分。

我们可以分链表长度为奇数和偶数讨论:

当长度为偶数:

当长度为奇数:

  • 那么**,第一步就先要得到链表的中间节点。我们可以用快慢指针**来实现:

定义两个指针fast、slow,同时指向链表头,slow每次走一个,fast每次走两个节点,当fast->next == NULL 或者 fast == NULL时,slow就走到中间节点了

struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && fast->next)
{
    slow = slow->next;
    fast = fast->next->next;
}
  • 第二步,就是反转以slow节点为头的链表,如果对单链表反转还不太了解的朋友,建议先看看👉反转单链表
struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL)
        return NULL;
    struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    newHead->next = head;
    struct ListNode* cur = head;
    while (cur->next)
    {
        struct ListNode* curNext = cur->next;
        cur->next = curNext->next;
        curNext->next = newHead->next;
        newHead->next = curNext;
    }
    struct ListNode* retHead = newHead->next;
    free(newHead);
    return retHead;
}
  • 第三步,我们用指针mid来接受slow后链表反转过后的头,接下来,从原来链表的头和mid开始比较,只要遇到不相等的情况,就返回false,否则返回true
struct ListNode* mid = reverseList(slow->next);
struct ListNode* cur1 = head;
struct ListNode* cur2 = mid;
while (cur1 && cur2)
{
    if (cur1->val != cur2->val)
    {
        return false;
    }
    cur1 = cur1->next;
    cur2 = cur2->next;
}
return true;
  • 最后一步,**在返回之前,需要将链表还原,**毕竟在现实生活中,没有人想再调用这个函数时改变原来的链表结构。但是,如果我们就按上面的操作进行还原,那么就会出现一系列的问题,我们拿下图说明

判断过后,链表的结构是这样的:

如果我们要将链表还原,那么问号处的节点的后面应该链接到reverseList(mid)的返回值,但问题是之前我们并没有保存问号处的节点。所以,我们可以对找到链表中间节点这一操作进行改进:

struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast->next && fast->next->next)
{
    slow = slow->next;
    fast = fast->next->next;
}

这样slow就会停留在问号处的位置,反转链表的时候就反转以slow->next为头的链表就行了

实现代码

struct ListNode* reverseList(struct ListNode* head) //反转链表
{
    if (head == NULL)
        return NULL;
    struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    newHead->next = head;
    struct ListNode* cur = head;
    while (cur->next)
    {
        struct ListNode* curNext = cur->next;
        cur->next = curNext->next;
        curNext->next = newHead->next;
        newHead->next = curNext;
    }
    struct ListNode* retHead = newHead->next;
    free(newHead);
    return retHead;
}
bool isPalindrome(struct ListNode* head){
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast->next && fast->next->next)  //找到中间节点的前一个节点
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    //反转以中间节点为头的链表
    //将返回值赋给mid
    struct ListNode* mid = reverseList(slow->next); 
    struct ListNode* cur1 = head;
    struct ListNode* cur2 = mid;
    bool ret = true;  //设置返回值
    while (cur1 && cur2)
    {
        if (cur1->val != cur2->val)
        {
      ret = false;  //只要出现不相等的情况,就将返回值设为false,推出比较
            break;
        }
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    //还原链表
    mid = reverseList(mid);
    slow->next = mid;
    //返回
    return ret;
}
相关文章
|
13天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
18 0
【数据结构OJ题】链表的回文结构
|
28天前
|
算法 C语言
【数据结构与算法 经典例题】链表的回文结构(图文详解)
【数据结构与算法 经典例题】链表的回文结构(图文详解)
|
2月前
题目----力扣--回文链表
题目----力扣--回文链表
25 0
|
2月前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
23 0
|
2月前
|
算法
【每日一题】牛客网——链表的回文结构
【每日一题】牛客网——链表的回文结构
|
2月前
|
C语言 C++ 索引
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表
|
2月前
|
Java Go C++
Golang每日一练(leetDay0086) 回文链表、删除链表节点
Golang每日一练(leetDay0086) 回文链表、删除链表节点
29 0
Golang每日一练(leetDay0086) 回文链表、删除链表节点
|
2月前
|
Python Java Go
Python每日一练(20230428) 最长有效括号、矩阵最长递增路径、回文链表
Python每日一练(20230428) 最长有效括号、矩阵最长递增路径、回文链表
41 0
Python每日一练(20230428) 最长有效括号、矩阵最长递增路径、回文链表
|
2月前
|
C++ Python Java
Python每日一练(20230424) 滑动窗口最大值、栈实现队列、直线上最多的点数
Python每日一练(20230424) 滑动窗口最大值、栈实现队列、直线上最多的点数
558 0
Python每日一练(20230424) 滑动窗口最大值、栈实现队列、直线上最多的点数
|
2月前
|
算法
链表的回文结构
链表的回文结构