Leetcode—234.回文链表【简单】

2023每日刷题（二十七）

Leetcode—234.回文链表

在这里插入图片描述

直接法实现代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool isPalindrome(struct ListNode* head) {
    if(head == NULL) {
        return true;
    }
    if(head->next == NULL) {
        return true;
    }
    if(head->next->next == NULL) {
        return head->next->val == head->val;
    }
    int len = 0;
    struct ListNode* p = head;
    while(p != NULL) {
        len++;
        p = p->next;
    }
    int *arr = (int *)malloc(sizeof(int) * len);
    p = head;
    int i = 0;
    while(p != NULL) {
        arr[i++] = p->val;
        p = p->next;
    }
    for(i = 0; i < len / 2; i++) {
        if(arr[i] != arr[len - 1 - i]) {
            return false;
        }
    }
    return true;
}

运行结果

在这里插入图片描述

快慢指针+链表原地逆置实现代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

// 找到中间节点
struct ListNode* midNode(struct ListNode* head) {
    struct ListNode* fast, *slow;
    fast = head;
    slow = head;
    while(fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 翻转链表
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* p = head, *q = head;
    struct ListNode* h = (struct ListNode*)malloc(sizeof(struct ListNode));
    h->next = NULL;
    while(p != NULL) {
        q = p->next;
        p->next = h->next;
        h->next = p;
        p = q;
    }
    return h->next;
}

bool isPalindrome(struct ListNode* head) {
    if(head == NULL) {
        return true;
    }
    if(head->next == NULL) {
        return true;
    }
    if(head->next->next == NULL) {
        return head->next->val == head->val;
    }
    struct ListNode* mid = midNode(head);
    struct ListNode* head2 = mid->next;
    head2 = reverseList(head2);
    while(head2 != NULL) {
        if(head->val != head2->val) {
            return false;
        }
        head = head->next;
        head2 = head2->next;
    }
    return true;
}