day3 回文链表

不懂一点编程。

读题

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

1
2
3
4
5
6
7
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) {}
};

有 next，有 val；没有 previous。

思路

考虑使用递归来实现遍历和反向遍历；使用一个全局的 list_length 对其进行计数；在反向遍历的时候启动下一次正向遍历，判断 val 是否相同。或者，首先计数一遍得到 list_length，之后再进行正反向遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int list_length = 0;

ListNode* cal_length(ListNode* root){
    if (root == nullptr) return false;
    list_length++;
    cal_length(root->next);
    return NULL;
}

ListNode* fun1(ListNode* root){
    if (root == nullptr) return false;
    if ()
}

ListNode* fun2(ListNode* root){
    
}

难点应该在于反向遍历时如何获取正向的数据？
考虑使用哈希表存储，哈希表能将指针与数据对应起来；需要对应指针和序号；获取了指针就能得到 val，因此不需要单独对 val 做映射。使用 num 作为正向前半段的序号，num_reverse 作为后半段的序号；num 的最大值就是链表的长度了，反向遍历的时候 num_reverse 从 0 开始，对应到前半段的序号；到 num/2 时停止。
递归好像和循环不一样，没办法中途停止？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int num = 0;
int num_reverse = 0;
bool ans = true; // 默认为回文
unordered_map<int, ListNode*> fa;

bool fun1(ListNode* root){
    if (root == nullptr) return false;
    fa[num] = root; // 从0开始算
    num++;
    ans = fun1(root->next);
    if (ans || (fa[num_reverse]->val != root->val)) return false;
    num_reverse++;
    return true;
}

结果测试案例通过，提交未通过，56 / 93 个通过的测试用例，仔细看了看有几处明显错误，比如没有 num_reverse++ 就直接 return 了。
修修补补之后的完整代码：
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
class Solution {
public:
    int num = 0;
    int num_reverse = 0;
    bool ans = true; // 默认为回文
    unordered_map<int, ListNode*> fa;

    bool fun1(ListNode* root){
        if (root == nullptr)
            return ans;
        fa[num] = root; // 从0开始算
        num++;
        ans = fun1(root->next);
        if (ans && (fa[num_reverse]->val == root->val)){
            num_reverse++;
            return true;
        }else {
            num_reverse++;
            return false;
        }
    }

    bool isPalindrome(ListNode* head) {
        if (head == nullptr) return false;
        fun1(head);
        return ans;
    }
};

结果

执行用时 252 ms，消耗内存 199.84 MB，大爆笑了，又慢又大坨。

优化

考虑到只需要存储前半的数据即可，于是先计算链表长度；当 num 和 num_reverse 超过一半时，停止判断，直接 return ans。

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
class Solution {
public:
    int num = 0;
    int num_reverse = 0;
    bool ans = true; // 默认为回文
    unordered_map<int, ListNode*> fa;
    int list_length = 0;

    void cal_length(ListNode* root){
        if (root == nullptr) return;
        list_length++;
        cal_length(root->next);
    }

    bool fun1(ListNode* root){
        if (root == nullptr) return true;
        if (num <= list_length/2) fa[num] = root; // 从0开始算
        num++;
        ans = fun1(root->next);
        if (num_reverse > list_length/2){
            num_reverse++;
            return ans;
        }
        if (ans && (fa[num_reverse]->val == root->val)){
            num_reverse++;
            return true;
        }else {
            num_reverse++;
            return false;
        }
    }

    bool isPalindrome(ListNode* head) {
        if (head == nullptr) return false;
        cal_length(head);
        fun1(head);
        return ans;
    }
};

用时 141 ms，内存 163.47 MB，没好到哪去。

官方题解

方法一：将值复制到数组中后用双指针法

也就是将链表转化为列表来做；还是经典的老面孔双指针法。列表好处是可以任意访问其中指定位置元素。值得注意的是，使用的是 vector 而不是我熟悉的原味数组 array，区别于 array，vector 是可变长的。
官方代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;
        while (head != nullptr) {
            vals.emplace_back(head->val);
            head = head->next;
        } // 拷贝到 vector 数组，拷贝完 head 直接弃用
        for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) {
            if (vals[i] != vals[j]) {
                return false;
            }
        }// 熟悉的双指针法
        return true;
    }
};

赏心悦目，简单高效。

方法二：递归

官方题解说：

1
2
3
4
5
6
7
8
递归为我们提供了一种优雅的方式来反向遍历节点。

function print_values_in_reverse(ListNode head)
    if head is NOT null
        print_values_in_reverse(head.next)
        print head.val

如果使用递归反向迭代节点，同时使用递归函数外的变量向前迭代，就可以判断链表是否为回文。

官方题解使用了两个指针，一内一外（而我是使用了一个指针和一个哈希表），当正向迭代完成后，自然会开始回溯/反向迭代；此时内部的指针在往回走，而外部的指针仍在 head 处正向走，于是可以轻易比较 val 的值，无需记录也无需统计长度。
值得注意的是，如果只是这样，仍然会 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
class Solution {
    ListNode* frontPointer; // 外面的指针
public:
    bool recursivelyCheck(ListNode* currentNode) {
        if (currentNode != nullptr) {
            if (!recursivelyCheck(currentNode->next)) { // 内指针前移
                return false;
            } // 如果上一轮判断是 false，那么跳过之后的代码，直接也返回 false
            if (currentNode->val != frontPointer->val) {
                return false;
            }// 判是否相等
            frontPointer = frontPointer->next;
            // 前向迭代结束后，外指针再随迭代前移
        }
        return true;
    }
    
    bool isPalindrome(ListNode* head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
};

中间 return 减少计算量的部分我也想到了，但是远没有这么优雅。

方法三：快慢指针

可以避免 O(n) 复杂度的神奇方法。具体思路是反转后半截链表，对比前后链表。步骤是：

  1. 找到前半部分链表的尾节点。
  2. 反转后半部分链表。
  3. 判断是否回文。
  4. 恢复链表。
  5. 返回结果。

其中第一步可以顺带统计链表长度，因此可以得知链表中点位置；不过，题解中使用的是快慢指针，快指针走两步，慢指针走一步，于是快指针走到尾的时候，慢指针恰好到达中点。于是有代码：

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
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode* firstHalfEnd = endOfFirstHalf(head);
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

        // 判断是否回文
        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool result = true;
        while (result && p2 != nullptr) {
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }

        // 还原链表并返回结果
        firstHalfEnd->next = reverseList(secondHalfStart);
        return result;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};

值得注意的是，这个方法只降低了空间复杂度，时间复杂度仍然是 O(n)。

收获

  1. 可以使用 vector 规避 array 的固定长度问题
  2. 快慢指针找中点
day3 回文链表
http://blog.wspdwzh.space/2025/10/20/day3-回文链表/
作者
peter？
发布于
2025年10月20日
许可协议