?
目錄
1、題目介紹
2、解題思路
2.1、暴力破解法
2.2、快慢指針反轉(zhuǎn)鏈表
?文章來源地址http://www.zghlxwxcb.cn/news/detail-713940.html
1、題目介紹
原題鏈接：?234. 回文鏈表 - 力扣（LeetCode）
示例 1：
輸入：head = [1,2,2,1]
輸出：true?
示例 2：
輸入：head = [1,2]
輸出：false?
提示：?
- 鏈表中節(jié)點數(shù)目在范圍[1, 10^5]?內(nèi)
- 0 <= Node.val <= 9
進階：你能否用?O(n)?時間復(fù)雜度和?O(1)?空間復(fù)雜度解決此題？
2、解題思路
判斷回文，就是判斷是否是對稱的。有些朋友對于數(shù)組的回文判斷非常熟悉，但是對鏈表的回文判斷可能就無從下手了，其實都一樣的。有一種非常簡單的方式就是將鏈表轉(zhuǎn)化成數(shù)組，然后就是判斷該數(shù)組是否回文就可以了，這種方式統(tǒng)稱暴力破解法，簡單粗暴。下面就來先帶著大家看一下這道題的暴力破解法。
2.1、暴力破解法
一共為兩個步驟：
- 復(fù)制鏈表值到數(shù)組列表中。
- 使用雙指針法判斷是否為回文。
首先按照題目要求的最大大小定義一個大小為100001的整型數(shù)組，接著通過循環(huán)遍歷將鏈表中每個結(jié)點的值取出放入數(shù)組中，最后通過兩個指針，一個從左一個從右分別判斷是否相等，只要遇到一個不相等就返回false，否則當(dāng)循環(huán)結(jié)束時返回true。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool isPalindrome(struct ListNode* head){
int arr[100001] = {0},num = 0;
while(head)
{
arr[num] = head->val;
head = head->next;
num++;
}
int i= 0;
int j =0;
for(i = 0,j = num-1; i<j; i++,j--)
{
if(arr[i]!=arr[j])
{
return false;
}
}
return true;
}時間復(fù)雜度：O(n)，其中 n 指的是鏈表的元素個數(shù)。
- 第一步：遍歷鏈表并將值復(fù)制到數(shù)組中，O(n)。
- 第二步：雙指針判斷是否為回文，執(zhí)行了 O(n/2) 次的判斷，即O(n)。
- 總的時間復(fù)雜度：O(2n)=O(n)。
空間復(fù)雜度：O(n)，其中 n 指的是鏈表的元素個數(shù)，我們使用了一個數(shù)組列表存放鏈表的元素值。
進階：你能否用?
O(n)?時間復(fù)雜度和?O(1)?空間復(fù)雜度解決此題？下面帶大家做一下本題的進階，使用快慢指針反轉(zhuǎn)鏈表實現(xiàn)空間復(fù)雜度為O(1)的算法。
2.2、快慢指針反轉(zhuǎn)鏈表
整個流程可以分為以下五個步驟：
- 找到前半部分鏈表的尾節(jié)點。
- 反轉(zhuǎn)后半部分鏈表。
- 判斷是否回文。
- 恢復(fù)鏈表。
- 返回結(jié)果。
對于第一步找到前半部分鏈表的尾結(jié)點，我們可以計算鏈表結(jié)點個數(shù)然后再找到前半部分的尾結(jié)點，也可以通過快慢指針一次遍歷找到前半部分的尾結(jié)點。
慢指針一次走一步，快指針一次走兩步，快慢指針同時出發(fā)。當(dāng)快指針移動到鏈表的末尾時，慢指針恰好到鏈表的中間。通過慢指針將鏈表分為兩部分。
此時slow就是前半部分的尾結(jié)點，而slow的下一個結(jié)點就是后半部分的頭結(jié)點。于是讓fast回到slow的next結(jié)點處，將后半部分的結(jié)點全部反轉(zhuǎn)，然后slow即前半部分的尾結(jié)點置空。
緊接著將讓slow從head重新出發(fā)，fast從最后結(jié)點出發(fā)，分別向中間結(jié)點靠近并判斷，只要相等就一直向中間靠近，遇到不相同時直接返回false，否則當(dāng)循環(huán)退出時返回true。
最后在將反轉(zhuǎn)鏈表還原回去即可。?
?代碼實現(xiàn)：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool isPalindrome(struct ListNode* head){
if(head == NULL || head->next == NULL)
{
return true;
}
struct ListNode* n1 = head;
struct ListNode* n2 = head;
//快慢指針遍歷
while(n2->next != NULL && n2->next->next != NULL)
{
n1 = n1->next; //慢指針
n2 = n2->next->next; //快指針
}
n2 = n1->next; //右邊第一個
n1->next = NULL;
struct ListNode* n3;
//反轉(zhuǎn)右半邊鏈表
while(n2 != NULL)
{
n3 = n2->next; //n3存放n2的next
n2->next = n1;
n1 = n2;
n2 = n3;
}
//當(dāng)循環(huán)結(jié)束時n1所指向的位置就是鏈表最后一個結(jié)點，
n2 = n3 = n1; //將n2和n3指回最后一個節(jié)點
n1 = head; //n1回到頭結(jié)點
bool flag = true;
//判斷是否是回文
while(n1 != NULL && n2 != NULL)
{
if(n1->val != n2->val)
{
flag = false;
break;
}
n1 = n1->next;
n2 = n2->next;
}
//還原鏈表
n2 = n3->next; //n3此時指向最后一個結(jié)點，因為反轉(zhuǎn)了鏈表，n3的next就是上一個結(jié)點
n3->next = NULL;
while(n2!=NULL)
{
n1 = n2->next;
n2->next = n3;
n3 = n2;
n2 = n1;
}
return flag;
}時間復(fù)雜度：O(n)，其中 n 指的是鏈表的大小。
空間復(fù)雜度：O(1)。我們只會修改原本鏈表中節(jié)點的指向，而在堆棧上的堆棧幀不超過 O(1)。
?更多【LeetCode刷題】?推薦：
【LeetCode力扣】86. 分隔鏈表-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133942678?spm=1001.2014.3001.5501【LeetCode力扣】297. 二叉樹的序列化與反序列化-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133827375【LeetCode力扣】LCR170 使用歸并排序的思想解決逆序?qū)栴}（詳細圖解）_Hacynn的博客-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133578735
?
如果覺得作者寫的不錯，求給博主一個大大的點贊支持一下，你們的支持是我更新的最大動力！文章來源：http://www.zghlxwxcb.cn/news/detail-713940.html
如果覺得作者寫的不錯，求給博主一個大大的點贊支持一下，你們的支持是我更新的最大動力！
如果覺得作者寫的不錯，求給博主一個大大的點贊支持一下，你們的支持是我更新的最大動力！
?
到了這里，關(guān)于【LeetCode力扣】234 快慢指針 | 反轉(zhuǎn)鏈表 | 還原鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
