正如標(biāo)題所說，本文會(huì)圖文詳細(xì)解析三道單鏈表OJ題，分別為：
- ?反轉(zhuǎn)鏈表 （簡(jiǎn)單）
- ?鏈表的中間節(jié)點(diǎn) （簡(jiǎn)單）
- ?鏈表的回文結(jié)構(gòu) （較難）
把他們放在一起講的原因是：?反轉(zhuǎn)鏈表 和?鏈表的中間節(jié)點(diǎn) 是?鏈表的回文結(jié)構(gòu) 的基礎(chǔ)
為什么這樣說？請(qǐng)往下看：
目錄
1. 反轉(zhuǎn)鏈表
做題思路
畫圖理解
代碼實(shí)現(xiàn)
2. 鏈表的中間節(jié)點(diǎn)
做題思路
畫圖理解
代碼實(shí)現(xiàn)
3. 鏈表的回文結(jié)構(gòu)
做題思路
畫圖理解
代碼實(shí)現(xiàn)
1. 反轉(zhuǎn)鏈表
LeetCode鏈接：206. 反轉(zhuǎn)鏈表 - 力扣（LeetCode）
??做題思路
- 遍歷鏈表，改變每個(gè)節(jié)點(diǎn)的鏈接方向，使其鏈向前節(jié)點(diǎn)
- 如果是第一個(gè)節(jié)點(diǎn)，使其鏈向 NULL?
這里需要3個(gè)指針：
- ?cur 指向當(dāng)前需要修改的節(jié)點(diǎn)
- ?prev 記錄?cur 的前一個(gè)節(jié)點(diǎn)， cur 要鏈向此節(jié)點(diǎn)
- ?next 記錄 cur 的后一個(gè)節(jié)點(diǎn)，避免 cur 改變鏈接方向后找不到下個(gè)節(jié)點(diǎn)
??畫圖理解
??代碼實(shí)現(xiàn)
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur = head;
struct ListNode* prev = NULL;
while (cur != NULL)
{
struct ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}最后提交代碼試試：
完美通過，本題并不難，來搞下一題
2. 鏈表的中間節(jié)點(diǎn)
LeetCode鏈接：876. 鏈表的中間結(jié)點(diǎn) - 力扣（LeetCode）
??做題思路
- 快慢指針
- 搞兩個(gè)指針，一個(gè)叫 fast ，一個(gè)叫 slow?
- 快指針 fast 一次走兩步
- 慢指針 slow 一次走一步
- 當(dāng) fast 走到 NULL 時(shí)， slow 恰好在中間，此時(shí) slow 指向的節(jié)點(diǎn)就是中間節(jié)點(diǎn)
??畫圖理解
??代碼實(shí)現(xiàn)
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}提交代碼：
這道題也很簡(jiǎn)單，主要就是快慢指針的思路，第一次接觸的話可能想不到這種方法
接下來就是本文重點(diǎn)了，前面這些只是開胃小菜
3. 鏈表的回文結(jié)構(gòu)
牛客鏈接：鏈表的回文結(jié)構(gòu)_?？皖}霸_?？途W(wǎng) (nowcoder.com)
??做題思路
1. 找到中間節(jié)點(diǎn)
2. 反轉(zhuǎn)中間節(jié)點(diǎn)及其之后的鏈表
3. 此時(shí)把鏈表分為兩段：
- 未反轉(zhuǎn)的鏈表為一段，用指針?list1 指向這段鏈表的頭節(jié)點(diǎn)
- 反轉(zhuǎn)過的鏈表為另一段，用指針 list2 指向這段鏈表的頭節(jié)點(diǎn)
4. 比較 list1 和 list2 節(jié)點(diǎn)的值是否相等
- 如果相等， list1 和 list2 同時(shí)往后走，去比較下一組數(shù)據(jù)
- 如果不相等，說明鏈表不是回文結(jié)構(gòu)，返回 false?
5. 當(dāng) list2 走到 NULL 處時(shí)，說明此鏈表是回文結(jié)構(gòu)，返回 true?
??畫圖理解
可以看到本題需要調(diào)用之前寫過的代碼
這就是為什么我說前兩道題是本題的基礎(chǔ)
??代碼實(shí)現(xiàn)
//找鏈表的中間節(jié)點(diǎn)
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
//反轉(zhuǎn)鏈表
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur = head;
struct ListNode* prev = NULL;
while (cur != NULL)
{
struct ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
//?？瓦@道題不支持用C語言答題
//雖然我們還沒有學(xué)C++，但是C++是兼容C的
//直接用C的方式寫代碼即可
class PalindromeList
{
public:
bool chkPalindrome(ListNode* head)
{
struct ListNode* list1 = head;
struct ListNode* mid = middleNode(head);
struct ListNode* list2 = reverseList(mid);
while (list2 != NULL)
{
if (list1->val != list2->val)
{
return false;
}
list1 = list1->next;
list2 = list2->next;
}
return true;
}
};提交代碼：
成功通過
怎么樣，大家看到這里把這三道題弄懂了嗎？如果有問題可以在評(píng)論區(qū)留言哦 :D文章來源：http://www.zghlxwxcb.cn/news/detail-646093.html
?本文完文章來源地址http://www.zghlxwxcb.cn/news/detail-646093.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】反轉(zhuǎn)鏈表、鏈表的中間節(jié)點(diǎn)、鏈表的回文結(jié)構(gòu)（單鏈表OJ題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
