Leetcode234. 回文链表

题目描述

请判断一个链表是否为回文链表。

示例 1:

1
2
输入: 1->2
输出: false

示例 2:

1
2
输入: 1->2->2->1
输出: true

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

解题思路

这道题的思路很简单。算法主要分为三部分：

  • 找出中间结点

中间结点可以通过快慢指针来寻找。设置两个指针，初始为首节点，然后一个指针一次走两步，一个指针一次走一步，当后一个指针走到末尾的时候，前一个指针指向的就是中间结点。

  • 将链表的后半部分反转

将链表的后半部分反转，那么就可以通过同步比较链表的前半部分和反转后的后半部分来判断是否是回文链表。

链表的反转可以用递归，也可以用迭代法实现，这两种算法会影响整体算法的空间复杂度。

链表反转的实现可以参看文章反转链表中的示例代码。

  • 对比判断链表的前半部分和反转后的后半部分来判断是否是回文链表

时间复杂度：O(n)O(n)

空间复杂度：O(1)O(1) 或者 $ O(n) $

当使用迭代法实现链表反转的时候，空间复杂度为O(1)O(1)；但是当用迭代法实现链表反转的时候，空间复杂度为 $ 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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) {}
};

ListNode* findMidPos(ListNode* head)
{
    if(head==nullptr||head->next==nullptr) return head;
    ListNode* pre=head;
    ListNode* cur=head;
    while(cur!=nullptr)
    {
        cur=cur->next;
        if(cur) cur=cur->next;
        pre=pre->next;
    }
    return pre;
}

ListNode* reverseList(ListNode* head)
{
    if(head==nullptr||head->next==nullptr) return head;
    ListNode* newHead=reverseList(head->next);
    head->next->next=head;
    head->next=nullptr;
    return newHead;
}

bool isPalindrome(ListNode* head)
{
    if(!head||!head->next) return true;
    ListNode* midPointer=findMidPos(head);
    ListNode* newHead=reverseList(midPointer);
    ListNode* first=head;
    ListNode* second=newHead;
    while(first&&second)
    {
        if(first->val!=second->val)
        {
            return false;
        }
        first=first->next;
        second=second->next;
    }
    return true;
}