LeetCode 234. Palindrome Linked List

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 234. Palindrome Linked List 原题链接简单

作者：

yxc , 2018-06-23 16:38:56 , 所有人可见 , 阅读 3489

10

6

题目描述

给定一个单链表，判断它是否是回文链表，即正着遍历和反着遍历得到的序列相同。

进一步： 能否只使用 $O(n)$ 的时间和额外 $O(1)$ 的空间？

样例1

输入：1->2
输出：false

样例2

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

算法

(链表操作) $O(n)$

我们先将链表的后半段翻转，然后用两个指针分别从链表首尾开始往中间扫描，依次判断对应节点的值是否相等，如果都相等，说明是回文链表，否则不是。

链表翻转参见 LeetCode 206. Reverse Linked List 中的 算法1——迭代翻转算法。

空间复杂度分析：链表的迭代翻转算法仅使用额外 $O(1)$ 的空间，所以本题也仅使用额外 $O(1)$ 的空间。
时间复杂度分析：整个链表总共被遍历4次，所以时间复杂度是 $O(n)$。

C++ 代码

/**
 * 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) {
        int n = 0;
        for (ListNode *p = head; p; p = p->next) n ++ ;
        if (n <= 1) return true;
        ListNode *a = head;
        for (int i = 0; i < (n + 1) / 2 - 1; i ++ ) a = a->next;
        ListNode *b = a->next;
        while (b)
        {
            ListNode *c = b->next;
            b->next = a;
            a = b;
            b = c;
        }
        b = head;
        ListNode *tail = a;
        bool res = true;
        for (int i = 0; i < n / 2; i ++ )
        {
            if (a->val != b->val)
            {
                res = false;
                break;
            }
            a = a->next;
            b = b->next;
        }
        a = tail, b = a->next;
        for (int i = 0; i < n / 2; i ++ )
        {
            ListNode *c = b->next;
            b->next = a;
            a = b;
            b = c;
        }
        tail->next = 0;
        return res;
    }
};

10 评论

有心人 2021-06-25 17:22

# 思路

# 代码

 class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int n = 0;
        for (auto p = head; p; p = p->next) n++;
        // 这里判断n<=1,否则下面 auto b=a->next;a可能=NULL, b->next出错
        if (n <=1) return true; 
        int half = n / 2;

        // 找到 后半部分头结点 a
        auto a = head;
        for (int i = 0; i < n - half; i++) a = a->next;

        // 反转 后半部分
        auto b = a->next;
        for (int i = 0; i < half - 1; i++){
            auto c = b->next;
            b->next = a;
            a = b, b = c;
        }
        auto tail = a; // 记录尾结点，最后恢复链表需要 tail->next=NULL

        // 判断是否回文, 不论是否回文 都要恢复链表
        bool res = true;
        auto left = head, right = a;
        for (int i = 0; i < half; i++){
            if (left -> val != right->val){
                res = false;
                break;
            }
            left = left->next, right = right->next;
        }

        // 恢复链表
        b = a->next;
        for (int i = 0; i < half - 1; i++){
            auto c = b->next;
            b->next = a;
            a = b, b = c;
        }
        tail->next = nullptr;

        return res;
    }
};

xju_wzp 2023-03-23 20:02

### 运用栈来判断是否为回文链表

解题思路：
1. 首先统计链表元素的总个数cnt，然后可通过元素的总个数求得链表的中点位置x = cnt / 2；
2. 定义cur = head，然后移动cur，将链表前半部分的x个元素依次入栈，最终cur指针指向第x元素的下一个元素；
3. 如果cnt为奇数，则要跳过当前cur指向的元素进行下一步判断；
4. 比较当前的cur指向的元素值是否等于栈顶元素：
- 若相等，则将栈顶元素删除，cur移动到下一个位置；
- 若不相等，则说明链表不是回文链表;
5. 最后判断链表是否为空：若为空，则为回文链表；反之，则不是。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int cnt = 0;
        stack<int> stk;
        for (auto cur = head; cur != nullptr; cur = cur->next) cnt++; //统计链表元素总个数
        int x = cnt / 2; //确定前半部分的元素个数
        auto cur = head;
        //前半部分链表元素值入栈操作
        while (x--) {
            stk.push(cur->val);
            cur = cur->next;
        }
        if (cnt % 2) cur = cur->next;
        //判断当前元素和栈顶元素是否相同
        while (cur) { 
            if (cur->val != stk.top()) return false; // 若不同，则不是回文链表
            else stk.pop(), cur = cur->next; // 若相同，栈顶元素出栈，然后接着比较下一个
        }
        if (stk.empty()) return true; // 最后若栈为空，则说明为回文元素
        return false;
    }
};

顾明诚 10个月前

也是很巧妙的

GainCompiler 2个月前

这两行可以不用

        if (stk.empty()) return true; // 最后若栈为空，则说明为回文元素
        return false;

蹲在街角〆仰望晴天ゞ 2020-10-23 09:49

我觉得可以使用快慢指针+链表反转可以少遍历一次

十一遇宁而停 9个月前

/
* 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:
stack [HTML_REMOVED] s;
vector[HTML_REMOVED] res;
bool isPalindrome(ListNode head) {
ListNode *p = head;
while(p){
res.push_back(p->val);
s.push(p->val);
p = p->next;
}
for(int i = 0;i < res.size();i++){
if(res[i] == s.top()){
s.pop();
}else return false;
}
return true;
}
};

饮花袜子 2023-05-04 08:03

/*
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
/
class Solution {
public boolean isPalindrome(ListNode head) {

    ListNode reversed = reverse(head);
    ListNode p1 = head, p2 = reversed;

    while (p1 != null && p2 != null)
    {
        if(p1.val != p2.val)    return false;
        System.out.println(p1.val);
        System.out.println(p2.val);
        p1 = p1.next;
        p2 = p2.next;
    }

    return true;


}

public ListNode reverse(ListNode head)
{
    if(head == null || head.next == null)
    {
        return head;
    }

    ListNode last = reverse(head.next);

    head.next.next = head;
    head.next = null;

    return last;
}

}
有好心人帮忙看看java算法，为什么不能通过[1, 1, 2, 1]测试吗？具体问题出在哪，虽然这个做法确实空间复杂度为O（n）了