链表的回文结构

目录

一.题目及剖析

二.思路引入

三.代码引入

四.扩展


一.题目及剖析

https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tab=note

众所周知,如果这道题的链表改为数组,这道题将十分简单,用左右指针就行,但人家说的是链表,显然左右指针是行不通的.

二.思路引入

1.找到链表的中间节点,将其分为两部分

2.将后半部分反转

3.如果反转后value与前半部分一样,则是回文结构

而前两步之前的我的博客有介绍

三.代码引入

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    struct ListNode* intermediateNode(struct ListNode* head)
    {
        struct ListNode* slow, *fast;
        slow = fast = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    struct ListNode* overturnList(struct ListNode* head)
    {
        struct ListNode *n1, *n2, *n3;
        n1 = NULL;
        n2 = n3 = head;
        if(head)
        n3 = head->next;
        while(n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if(n3)
            n3 = n3->next;
        }
        return n1;
    }
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* pcur = intermediateNode(A);
        struct ListNode* prev = overturnList(pcur);
        while(prev)
        {
            if(A->val != prev->val)
            return false;
            prev = prev->next;
            A = A->next;
        }
        return true;
    }
};

四.扩展

当然对于这道题,我们还可以有其他的解法,比如遍历这个链表,将其中的value存放至一个数组中,然后我们就可以使用左右指针去解决,这个算法的时间复杂度是o(n+logn),而第一种方法的时间复杂度是o(n)

相关推荐

  1. (对称)结构

    2024-02-17 08:36:03       17 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-02-17 08:36:03       19 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-02-17 08:36:03       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-02-17 08:36:03       19 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-02-17 08:36:03       20 阅读

热门阅读

  1. 【图论经典题目讲解】洛谷 P2371 墨墨的等式

    2024-02-17 08:36:03       32 阅读
  2. 紫微斗数全书卷一斗数太微赋

    2024-02-17 08:36:03       28 阅读
  3. 力扣热题100_双指针_15_三数之和

    2024-02-17 08:36:03       26 阅读
  4. Rust 初体验5

    2024-02-17 08:36:03       28 阅读
  5. truncate、delete、drop的区别?

    2024-02-17 08:36:03       33 阅读
  6. logger 记录

    2024-02-17 08:36:03       26 阅读