链表的回文结构_牛客题霸_牛客网对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为。题目来自【牛客题霸】https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

题目

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

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

测试样例：

1->2->2->1

返回：true

 本题用到了链表的逆转和链表的中间节点的应用

首先说一下链表的中间节点的查找

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

  }

 中间结点的查找主要运用到了快慢指针的遍历。快指针比慢指针多走一步，最后快指针走到NULL，或者快指针的next为NULL停止。

再来说一下链表的逆转

struct ListNode* reverselist(struct ListNode*head)
{
    struct ListNode*prve= NULL;
    struct ListNode*cur=head;
    while(cur)
    {
        struct ListNode*next=cur->next;
        cur->next=prve;
        prve=cur;
        cur=next;
    }
    return prve;
}

逆转的本质是要先定义一个空指针，如上代码的*prve，然后下一步就开始保存cur的下一个指针，防止cur被覆盖，导致下一个节点丢失。最后返回prve即可。原因是这是的cur已经指向NULL，所以无意义。

最后是实现链表回文（注意：C++兼容C语言）

#include <algorithm>
class PalindromeList {
public:

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

  }
struct ListNode* reverselist(struct ListNode*head)
{
    struct ListNode*prve= NULL;
    struct ListNode*cur=head;
    while(cur)
    {
        struct ListNode*next=cur->next;
        cur->next=prve;
        prve=cur;
        cur=next;
    }
    return prve;
}

    bool chkPalindrome(ListNode* A) {
struct ListNode* mid=midfind(A);
struct ListNode* revermid=reverselist(mid);
while(revermid&&A)
{
   if(revermid->val!=A->val)
   {
    return false;
}
revermid=revermid->next;
       A=A->next;
    }
    return true;
}

};