【LeetCode】234. 回文链表

前言

为了养成创作习惯，从今天起开始刷力扣了，只刷简单和中等难度的题，分类刷，这个月就先刷链表题，从简单的开始按着顺序刷，一天一道，养生做法。

为了锻炼一下自己，决定用 C 来写，据说是受苦，不过一天一道无所谓了。

题目描述

234. 回文链表 - 力扣（LeetCode）

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

示例 & 提示

示例 1：

输入：head = [1,2,2,1]
输出：true
复制代码
1
2
3

示例 2：

输入：head = [1,2]
输出：false
复制代码
1
2
3

提示：

[1, 105]
0 <= Node.val <= 9

1
2
3

思路

• 暴力就是把链表值复制到一个数组里，然后双指针比较

• 首先我们需要找到中间结点，然后将后面的结点逆置，前段和后段对比即可

• 又或者我们可以换个思路，比如在找中间结点的时候逆置前半部分？这样如果是奇数个元素，需要多判断一下

• 最后还有递归做法，我们都知道可以用递归反向打印链表，思路这不就有了

具体代码

bool isPalindrome(struct ListNode *head) {
	if (head == NULL || head->next == NULL) {
        return true;
    }

    struct ListNode *slow = head, *fast = head, *pre, *tmp;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    pre = slow;
    slow = slow->next;
    pre->next = NULL;
    while (slow != NULL) {
        tmp = slow->next;
        slow->next = pre;
        pre = slow;
        slow = tmp;
    }

    while (pre != NULL) {
        if (head->val != pre->val) {
            return false;
        }
        pre = pre->next;
        head = head->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
25
26
27
28
29
30
31

bool isPalindrome(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return true;
    }

    struct ListNode *slow = head, *fast = head, *pre = NULL, *cur;
    while (fast != NULL && fast->next != NULL) {
        cur = slow;
        slow = slow->next;
        fast = fast->next->next;

        cur->next = pre;
        pre = cur;
    }

    if (fast != NULL) {
        slow = slow->next;
    }

    while (cur != NULL) {
        if (cur->val != slow->val) {
            return false;
        }
        cur = cur->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
25
26
27
28
29

struct ListNode *tmp;
bool check(struct ListNode *head) {
    if (head == NULL) {
        return true;
    }
    bool res = check(head->next) && (tmp->val == head->val);
    tmp = tmp->next;
    return res;
}

bool isPalindrome(struct ListNode *head) {
    tmp = head;
    return check(head);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14