当前位置：首页 > article >正文

L10.【LeetCode笔记】回文链表

article 2024/11/14 4:45:25

1.题目

2.自解

代码

提交结果

1.题目

给你一个单链表的头节点 head ，请你判断该链表是否为

回文链表

。如果是，返回 true ；否则，返回 false 。

示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：

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

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

代码模板
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool isPalindrome(struct ListNode* head) 
{
}

2.自解

一个容易想到的方法:将链表的每个节点的val存入一个数组中,最后用双指针访问

有关双指针判断回文链表的思想参见L8.【LeetCode笔记】回文数

代码

bool isPalindrome(struct ListNode* head) 
{
    int arr[100000]={0};
    int i=0; 
    struct ListNode* cur=head; 
    while (cur)
    {
        arr[i]=cur->val;
        i++;
        cur=cur->next;
    }
    int* left=&arr[0];
    int* right=&arr[i-1];
    while (left<right)
    {
        if (*left==*right)
        {
            left++;
            right--;
        }
        else
        return false;
   }
   return true;
}