大家好，我是安然无虞。

每篇前言

博客主页：安然无虞

作者认证：2021年博客新星Top2

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请铁汁批评斧正。

火爆专栏：蓝桥杯基础算法剖析
欢迎加入：比特社区

种一棵树最好的时间是十年前，其次是现在。 各位，共勉。

面试题：回文链表

原题链接：回文链表
题目描述：
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。
示例：
1->2->2->1
返回：true

解题思路

之所以讲解前面两题，实际上都是为这道题准备的，本题的解题步骤是：

• 找出链表的中间位置；
• 逆置后半段
• 最后从头依次比较即可

代码执行：

//回文链表
class PalindromeList {
public:
   //判断中间结点
   struct ListNode* middleNode(struct ListNode* A)
   {
       struct ListNode* slow = A, *fast = A;
       while(fast && fast->next)
       {
           slow = slow->next;
           fast = fast->next->next;
       }
     return slow;
 }
   //反转后半部分
   struct ListNode* reverseAfter(struct ListNode* mid)
   {
       struct ListNode* newHead = NULL, *cur = mid;
       while(cur)
       {
           struct ListNode* next = cur->next;
           cur->next = newHead;
           newHead = cur;
           cur = next;
       }
       return newHead;
   }
   bool chkPalindrome(ListNode* A) 
   {
       // write code here
       //先判断中间结点
       struct ListNode* mid = middleNode(A);
       //再反转后半部分
       struct ListNode* rHead = reverseAfter(mid);
       while(A && rHead)
       {
           if(A->val != rHead->val)
           {
               return false;
           }
           else
           {
               A = A->next;
               rHead = rHead->next;
           }
      }
       return true;
   }
};

   

  

   
1
   
2
   
3
   
4
   
5
   
6
   
7
   
8
   
9
   
10
   
11
   
12
   
13
   
14
   
15
   
16
   
17
   
18
   
19
   
20
   
21
   
22
   
23
   
24
   
25
   
26
   
27
   
28
   
29
   
30
   
31
   
32
   
33
   
34
   
35
   
36
   
37
   
38
   
39
   
40
   
41
   
42
   
43
   
44
   
45
   
46
   
47
   
48
   
49
  

完整代码：

遇见安然遇见你，不负代码不负卿。

码字不易，求个三连 抱拳了兄弟们。

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/123991256