1.题目

2.思路

如果不要求$O(1)$空间复杂度，即可以用栈；而按现在的要求，可以将后半链表就行翻转（【LeetCode206】反转链表（迭代or递归）），再将2段 半个链表进行比较判断即可达到$O(1)$的空间复杂度——注意判断比较的是val值，不要误以为比较指针。。

可以举个上面的栗子看看[1，1，2，1]，注意fast是指到后面的NULL，而不是第一个位置停住，此时slow2停住的位置是链表的中间位置（偏下半部分，如果结点个数为奇数则是中间节点）。

注意：由于上面栗子操作完后，slow1指向的1结点的next指针还会指向2结点，但是不影响后面判断（2结点的next指向NULL所以会跳出while循环），所以上述说的指向的指针不必理会。

3.代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast && fast->next){//slow指向链表的中间结点(偏右)
            slow=slow->next;
            fast=fast->next->next;
        }
        if(slow->next==NULL){//当[1,2]时用时，不过这个if可省略
            if(slow->val!=head->val)
                return false;
            else 
                return true;
        }
        ListNode* tail=reverseList(slow);
        //slow->next=NULL;
        while(head!=NULL && tail!=NULL){
            if(head->val == tail->val){//千万不要少了val
                head=head->next;
                tail=tail->next;
            }else{
                return false;
            }
        }
        return true;
    }
    ListNode* reverseList(ListNode* head){//反转链表
        ListNode* slow=NULL;
        ListNode* fast=head;
        ListNode* temp;
        while(fast){
            temp=fast->next;//临时结点，保存fast的下一个结点
            fast->next=slow;
            slow=fast;
            fast=temp;
        }
        return slow;
    }
};

  

 

  
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
  
50
 

4.递归法

如果不考虑$O(1)$的空间复杂度，用递归也挺巧妙的。

用一个全局变量p记录正向起始点，然后调用递归，因为递归退栈的时候可以反向遍历链表的节点，所以我们正反可以同时向中间移动，判断是否是回文链表。

class Solution {
    ListNode *p;        //起始头结点
    bool flag = true;   
public:
    bool isPalindrome(ListNode* head) {
        p = head;
        check(head);
        return flag;
    }
    void check(ListNode* head) {
        if(head == NULL)    return ;
        check(head->next);
        if(p->val != head->val) flag = false;
        p = p->next;    //移动正向的指针
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/116035438