【LeetCode】234. 回文链表
2022-08-19 本文已影响0人
Java技术人
前言
为了养成创作习惯，从今天起开始刷力扣了，只刷简单和中等难度的题，分类刷，这个月就先刷链表题，从简单的开始按着顺序刷，一天一道，养生做法。
为了锻炼一下自己，决定用 C 来写，据说是受苦，不过一天一道无所谓了。
题目描述
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 & 提示
示例 1：
<pre class="prettyprint hljs lua" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", 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, "Courier New", 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, "Courier New", 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, "Courier New", 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, "Courier New", 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, "Courier New", 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>
