【LeetCode】234. 回文链表

前言

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

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

题目描述

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

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

示例 & 提示

示例 1：

<pre class="prettyprint hljs lua" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">输入：head = [1,2,2,1]
输出：true
复制代码</pre>

示例 2：

<pre class="prettyprint hljs lua" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">输入：head = [1,2]
输出：false
复制代码</pre>

提示：

<pre class="hljs makefile" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 0.75em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">[1, 105]
0 <= Node.val <= 9
</pre>

思路

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

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

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

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

具体代码

<pre class="prettyprint hljs elixir" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">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;
}
复制代码</pre>

<pre class="prettyprint hljs php" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">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;
}
复制代码</pre>

<pre class="prettyprint hljs rust" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; overflow-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">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);
}</pre>