前言
為了養(yǎng)成創(chuàng)作習慣，從今天起開始刷力扣了，只刷簡單和中等難度的題，分類刷，這個月就先刷鏈表題，從簡單的開始按著順序刷，一天一道，養(yǎng)生做法。
為了鍛煉一下自己，決定用 C 來寫，據(jù)說是受苦，不過一天一道無所謂了。
題目描述
給你一個單鏈表的頭節(jié)點 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>
思路
暴力就是把鏈表值復制到一個數(shù)組里，然后雙指針比較
首先我們需要找到中間結點，然后將后面的結點逆置，前段和后段對比即可
又或者我們可以換個思路，比如在找中間結點的時候逆置前半部分？這樣如果是奇數(shù)個元素，需要多判斷一下
最后還有遞歸做法，我們都知道可以用遞歸反向打印鏈表，思路這不就有了
具體代碼
<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>
