[数据结构]-链表回文结构判断_回文检测数据结构

目录

回文结构判断

一、中间结点

二、链表翻转

三、全部代码

---

回文结构判断

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

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

测试样例：1->2->2->1          return:true

                  1->2->3->2->1     return:true

                  1->2->4->3          return:false

原题目：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

分为以下两种情况讨论，只需要找到中间结点，然后记录中间结点地址并翻转。将反转后的链表和原链表进行比较即可判断原链表是否为回文。

---

---

一、中间结点

 首先来讲解一下如何使用一次遍历来找到单链表的中间结点。

用到了常见的双指针，其中分别为快指针和慢指针。快指针一次遍历两个结点，慢指针一次遍历一个结点。

具体代码如下：

    //找出中间结点
    struct ListNode* MiddleNode(struct ListNode* head)
    {
        struct ListNode* fast = head;
        struct ListNode* slow = head;
        //快指针为NULL或快指针的下一个节点为NULL跳出循环
        while( fast && fast->next )
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

---

二、链表翻转

 接下来讲解如何使用反转链表。

此时需要三指针，需要记录当前节点的前一结点，当前结点和当前结点的下一结点。

具体代码如下：

//对中间结点开始的链表进行翻转
    struct ListNode* reverseList(struct ListNode* head)
    {
        struct ListNode* cur = head;
        struct ListNode* newhead = NULL;
        struct ListNode* next;
        while(cur)
        {
            next = cur->next; 
            
            //头插法
            cur->next = newhead;
            newhead = cur;
 
            cur = next;
        } 
        return newhead;
    }

---

三、全部代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    
    //找出中间结点
    struct ListNode* MiddleNode(struct ListNode* head)
    {
        struct ListNode* fast = head;
        struct ListNode* slow = head;
 
        while( fast && fast->next )
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    
    //对中间结点开始的链表进行翻转
    struct ListNode* reverseList(struct ListNode* head)
    {
        struct ListNode* cur = head;
        struct ListNode* newhead = NULL;
        struct ListNode* next;
        while(cur)
        {
            next = cur->next; 
            
            //头插法
            cur->next = newhead;
            newhead = cur;
 
            cur = next;
        } 
        return newhead;
    }
  
 
    bool chkPalindrome(ListNode* A)
    {
        struct ListNode* cur = A;
 
        struct ListNode* Middle = MiddleNode(A);
 
        struct ListNode* New = reverseList(Middle);
 
        while(cur && New)
        {
            if(cur->val != New->val)
                return false;
            
            cur = cur->next;
            New = New->next;
            
        }
        return true;     
    }
};