链表的回文结构_链表回文结构

目录

一.题目及剖析

二.思路引入

三.代码引入

四.扩展

---

一.题目及剖析

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

描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

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

二.思路引入

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)