24 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为 回文链表。如果是，返回 true ；否则，返回 false 。

题解1 栈

/**
 * 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) {
        stack<ListNode*> kstack;
        ListNode* tmp = head;
        while(tmp){
            kstack.push(tmp);
            tmp = tmp->next;
        }
        while(kstack.size()){
            if(kstack.top()->val != head->val){
                return 0;
            }
            kstack.pop();
            head = head->next;
        }
        return 1;
    }
};
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

题解2 基础链表递归（思路）

class Solution {
    ListNode* frontPointer;
public:
    bool recursivelyCheck(ListNode* currentNode){
        if(currentNode){
            // 递归到尾结点，返回true，这里主要为了下一步判断的终止
            if(! recursivelyCheck(currentNode->next)){
                return false;
            }
            // 递归结束开始弹栈
            if(currentNode->val != frontPointer->val){
                return false;
            }
            // 全局指针，配合栈往后移
            frontPointer = frontPointer->next;
        }
        // 到NULL 返回true
        return true;
    }
    bool isPalindrome(ListNode* head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

题解3 双指针

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* fastN;
        ListNode* slowN = fastN = head;
        // fastN 移动到链表末尾 slowN移到链表中间(后半段开始的位置)
        while(fastN && fastN->next){
            fastN = fastN->next->next;
            slowN = slowN->next;  
        }
        ListNode* pre = nullptr;
        while(slowN){
            ListNode* tmp = slowN->next;
            slowN->next = pre;
            pre = slowN;
            slowN = tmp;
        }
        ListNode* tmpP = pre;
        // 判断
        while(pre){
            if(head->val != pre->val)
                return 0;
            head = head->next;
            pre = pre->next;
        }
       
        // 把链表修正回来（可有可无，本题没要求）
        ListNode* ppre = nullptr;
        while(tmpP){
            ListNode* tmp = tmpP->next;
            tmpP->next = ppre;
            ppre = tmpP;
            tmpP = tmp;
        }
        return 1;
    }
};
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