Leetcode（234）——回文链表_回文链表 leetcode

Leetcode（234）——回文链表

题目

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

示例 1：

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

示例 2：

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

提示：

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

进阶：你能否用 $O(n)$ 时间复杂度和 $O(1)$ 空间复杂度解决此题？

题解

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

思路

​​  一共为两个步骤：

• 复制链表值到数组列表中。
• 使用双指针法判断是否为回文。

​​  第一步，我们需要遍历链表将值复制到数组中。我们用 currentNode 指向当前结点。每次迭代向数组添加 currentNode.val，并更新 currentNode = currentNode.next，当 currentNode = null 时停止循环。

​​  执行第二步的最佳方法取决于你使用的语言。在 Python 中，很容易构造一个列表的反向副本，也很容易比较两个列表。而在其他语言中，就没有那么简单。因此最好使用双指针法（双下标）来检查是否为回文。我们在起点放置一个指针，在结尾放置一个指针，每一次迭代判断两个指针指向的元素是否相同，若不同，返回 false；相同则将两个指针向内移动，并继续判断，直到两个指针相遇。

​​  在编码的过程中，注意我们比较的是结点值的大小，而不是结点本身。正确的比较方式是：node_1.val == node_2.val，而 node_1 == node_2 是错误的。

代码实现

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;
        while (head != nullptr) {
            vals.emplace_back(head->val);
            head = head->next;
        }
        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
9
10
11
12
13
14
15
16

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 指的是链表的元素个数。

• 第一步： 遍历链表并将值复制到数组中，$O(n)$。
• 第二步：双指针判断是否为回文，执行了 $O(n/2)$ 次的判断，即 $O(n)$。
  总的时间复杂度：$O(2n)=O(n)$。

空间复杂度：$O(n)$，其中 $n$ 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。

方法二：递归

思路

​​  为了想出使用空间复杂度为 $O(1)$ 的算法，你可能想过使用递归来解决，但是这仍然需要 $O(n)$ 的空间复杂度。

​​  递归为我们提供了一种优雅的方式来方向遍历结点。

function print_values_in_reverse(ListNode head)
    if head is NOT null
        print_values_in_reverse(head.next)
        print head.val
1
2
3
4

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

算法

​​  currentNode 指针是先到尾结点，由于递归的特性再从后往前进行比较。frontPointer 是递归函数外的指针。若 currentNode.val != frontPointer.val 则返回 false。反之，frontPointer 向前移动并返回 true。

​​  算法的正确性在于递归处理结点的顺序是相反的（回顾上面打印的算法），而我们在函数外又记录了一个变量，因此从本质上，我们同时在正向和逆向迭代匹配。

​​  计算机在递归的过程中将使用堆栈的空间，这就是为什么递归并不是 $O(1)$ 的空间复杂度。

代码实现

class Solution {
    ListNode* frontPointer;
public:
    bool recursivelyCheck(ListNode* currentNode) {
        if (currentNode != nullptr) {
            if (!recursivelyCheck(currentNode->next)) {
                return false;
            }
            if (currentNode->val != frontPointer->val) {
                return false;
            }
            frontPointer = frontPointer->next;
        }
        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

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 指的是链表的大小。
空间复杂度：$O(n)$，其中 $n$ 指的是链表的大小。我们要理解计算机如何运行递归函数，在一个函数中调用一个函数时，计算机需要在进入被调用函数之前跟踪它在当前函数中的位置（以及任何局部变量的值），通过运行时存放在堆栈中来实现（堆栈帧）。在堆栈中存放好了数据后就可以进入被调用的函数。在完成被调用函数之后，他会弹出堆栈顶部元素，以恢复在进行函数调用之前所在的函数。在进行回文检查之前，递归函数将在堆栈中创建 $n$ 个堆栈帧，计算机会逐个弹出进行处理。所以在使用递归时空间复杂度要考虑堆栈的使用情况。

这种方法不仅使用了 $O(n)$ 的空间，且比第一种方法更差，因为在许多语言中，堆栈帧的开销很大（如 Python），并且最大的运行时堆栈深度为 1000（可以增加，但是有可能导致底层解释程序内存出错）。为每个结点创建堆栈帧极大的限制了算法能够处理的最大链表大小。

方法三：快慢指针 + 翻转链表 + 边遍历边翻转（前半部分）

思路

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

• 找到前半部分链表的尾结点，在遍历的时候通过慢指针反转前半部分链表。
• 判断是否回文。
• 恢复链表。
• 返回结果。

​​  步骤一我们可以计算链表结点的数量，然后遍历链表找到前半部分的尾结点。
​​  我们也可以使用 快慢指针 在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
​​  若链表有奇数个结点，则中间的结点不参与对比。
​​  在快慢指针遍历链表的时候，也开始反转链表的前半部分。——相比先让快慢指针遍历完链表再反战后半部分的链表，这减少了遍历一半链表的时间。

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

​​  步骤三再反转一次恢复链表本身。

代码实现

两个最后没有恢复链表的写法（最好还是要恢复，因为一般调用该算法的人不想别人修改自己的数据）：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return true;
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* pre = head;
        ListNode* pre_pre = nullptr;
        while(fast != nullptr && fast->next != nullptr){
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
            pre->next = pre_pre;
            pre_pre = pre;
        }
        if(fast != nullptr) slow = slow->next;
        while(pre != nullptr){
            if(pre->val != slow->val) return false;
            pre = pre->next;
            slow = slow->next;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr) return true;
        if(head->next && !head->next->next){
           if(head->val == head->next->val) return true;
           else return false;
        }
        ListNode* second=nullptr;
        ListNode* first=divi_reverse(head,second);
        while(first && second){
            if(first->val != second->val) return false;
            first=first->next;
            second=second->next;
        }
        return true;
    }

    ListNode* divi_reverse(ListNode* head,ListNode*& tmp) {
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* second=head->next;
        ListNode* third=nullptr;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            third=second->next;
            second->next=slow;
            slow=second;
            second=third;
        }
        tmp=third;
        head->next=nullptr;
        return fast->next==nullptr?slow->next: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

复杂度分析

时间复杂度：$O(n)$ ，其中 $n$ 指的是链表的大小。
空间复杂度：$O(1)$