题目

判断一个单链表是不是回文

1
2
Input: 1->2->3->2->1
Output: true

方法一 额外空间

需要一个vector存放元素，时间复杂度O(n), 空间复杂度O(n)

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vec;
        ListNode* point = head;
        while (point) {
            vec.push_back(point->val);
            point = point->next;
        }
        return isPalHelper(vec);
    }
    
    bool isPalHelper(vector<int> vec) {
        int i = 0, j = vec.size()-1;
        while (i < j) {
            if (vec[i] == vec[j]) {
                i++;
                j--;
            } else {
                return false;
            }
        }
        return true;
    }
};

方法二 不需要额外空间

使用两个不同步进的指针来找到中间节点，将中间节点到终点这一段反转后，一一比对直到结尾。时间复杂度O(n), 空间复杂度O(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
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head) return true;
        ListNode* point = head, *fast = head;
        while (fast->next && fast->next->next) {  // 找到中点
            point = point->next;
            fast = fast->next->next;
        }
        if (!point) return false;
        point = point->next; // 右半边的第一个节点
        point = reverse(point);
        while (head && point) { // 反转后一个一个比对
            if (head->val != point->val) return false;
            head=head->next;
            point=point->next;
        }
        return true;
    }
    
    ListNode* reverse(ListNode* head) { // 将右半边链表反转
        ListNode* prev = nullptr, *point = head, *next = nullptr;
        while (point) {
            ListNode* next = point->next;
            point->next = prev;
            prev = point;
            if (!next) {
                head = point;
            }
            point = next;
        }
        return head;
    }
};