📝 题目描述

题目链接：回文链表

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

回文序列：回文序列是向前和向后读都相同的序列。

示例：

示例 1：

1
2
输入：head = [1,2,2,1]
输出：true

示例 2：

1
2
输入：head = [1,2]
输出：false

提示：

  • 链表中节点数目在范围[1, 10^5] 内
  • 0 <= Node.val <= 9

💡 解题思路

方法一：复制到数组

这个思路很直观也很简单，就是复制一份数字到数组中去，再利用双指针进行回文判断。

方法二：递归

实际上就是借助栈的性质实现逆序比较。

这种方法需要在递归函数外部预留一个ListNode*的变量，每当返回一层递归，全局变量就要往后移动一个节点，以便进行对比。

方法三：快慢指针

我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。

该方法虽然可以将空间复杂度降到 O(1)，但是在并发环境下，该方法也有缺点。在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。

整个流程可以分为以下五个步骤：

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

执行步骤一，我们可以计算链表节点的数量，然后遍历链表找到前半部分的尾节点。

我们也可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

若链表有奇数个节点，则中间的节点应该看作是前半部分。

步骤二可以使用「206. 反转链表」问题中的解决方法来反转链表的后半部分。

步骤三比较两个部分的值，当后半部分到达末尾则比较完成，可以忽略计数情况中的中间节点。

步骤四与步骤二使用的函数相同，再反转一次恢复链表本身。

🔧 代码实现

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
/**
 * 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) {
        vector<int> valList;
        ListNode * ptr = head;
        while(ptr) {
            valList.push_back(ptr -> val);
            ptr = ptr -> next;
        }
        int left = 0, right = valList.size() - 1;
        while(left < right) {
            if (valList[left] != valList[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

2、递归

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
/**
 * 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:
    // 预留一个外部指针
    ListNode* publicPtr;
    bool recursivelyCheck(ListNode * ptr) {
        // 不为空指针，说明正在返回
        if (ptr != nullptr) {
            // 先看前面返回的答案，如果是false就不再需要比较了，直接将false逐层返回即可
            if (recursivelyCheck(ptr -> next)) {
                // 如果是true，则比较自己的这一层
                if (ptr -> val != publicPtr -> val) {
                    return false;
                } else {
                    // 将外部指针往后移动一个节点
                    publicPtr = publicPtr -> next;
                    return true;
                }
            } else {
                return false;
            }
        }
        return true;
    }
    bool isPalindrome(ListNode* head) {
        // 初始化预留的指针
        publicPtr = head;
        return recursivelyCheck(head);
    }
};

3、快慢指针

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;
    }
};

📊 复杂度分析

1、复制到数组

  • 时间复杂度：O(n)O(n)，其中 n 指的是链表的元素个数。复制+双指针遍历 = 2×n2 \times n。
  • 空间复杂度：O(n)O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。

2、递归

  • 时间复杂度：O(n)O(n)，其中 n 指的是链表的大小。
  • 空间复杂度：O(n)O(n)，其中 n 指的是链表的大小。我们要理解计算机如何运行递归函数，在一个函数中调用一个函数时，计算机需要在进入被调用函数之前跟踪它在当前函数中的位置（以及任何局部变量的值），通过运行时存放在堆栈中来实现（堆栈帧）。在堆栈中存放好了数据后就可以进入被调用的函数。在完成被调用函数之后，他会弹出堆栈顶部元素，以恢复在进行函数调用之前所在的函数。在进行回文检查之前，递归函数将在堆栈中创建 n 个堆栈帧，计算机会逐个弹出进行处理。所以在使用递归时空间复杂度要考虑堆栈的使用情况。这种方法不仅使用了 O(n)O(n) 的空间，且比第一种方法更差，因为在许多语言中，堆栈帧的开销很大（如 Python），并且最大的运行时堆栈深度为 1000（可以增加，但是有可能导致底层解释程序内存出错）。为每个节点创建堆栈帧极大的限制了算法能够处理的最大链表大小。

3、快慢指针

  • 时间复杂度：O(n)O(n)，其中 n 指的是链表的大小。
  • 空间复杂度：O(1)O(1)，我们只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)O(1)。

🎯 总结

  • 核心思想：明白递归的写法。