柚子快報激活碼778899分享：輕觸節(jié)點，鏈表里的悄然邂逅
公主請閱
1. 移除鏈表元素1. 題目說明示例 1示例 2示例 3
1.2 題目分析1.3 代碼部分1.4 代碼解析
2. 反轉(zhuǎn)鏈表2. 1題目說明示例 1示例 2示例 3
2.2 題目分析2.3 代碼部分2.4 代碼分析
1. 移除鏈表元素
題目傳送門
1. 題目說明
給你一個鏈表的頭節(jié)點 head 和一個整數(shù) val ，請你刪除鏈表中所有滿足 Node.val == val 的節(jié)點，并返回 新的頭節(jié)點 。
示例 1
輸入：head = [1,2,6,3,4,5,6], val = 6 輸出：[1,2,3,4,5]
示例 2
輸入：head = [], val = 1 輸出：[]
示例 3
輸入：head = [7,7,7,7], val = 7 輸出：[]
1.2 題目分析
題目給了我們一個鏈表，要求說讓我們將值等于val的鏈表刪除，并且返回新的頭結(jié)點 那么這個題我們該怎么進行解決呢？ 我的想法是：我們可以通過設(shè)置一個哨兵位然后利用雙指針進行鏈表的遍歷，然后我們的兩個指針如果在遍歷過程中遇到了滿足條件的節(jié)點的話，我們直接忽略了，將這個節(jié)點的前一個節(jié)點的next的指針進行改變，指向這個節(jié)點的下一個節(jié)點，通過這種方法我們間接的將這個節(jié)點刪除了
1.3 代碼部分
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val)
{
//創(chuàng)建一個哨兵節(jié)點(tmp)，哨兵節(jié)點的next指針指向頭結(jié)點
struct ListNode*tmp=(struct ListNode*)malloc(sizeof(struct ListNode));
tmp->next=head;
//雙指針
struct ListNode*prev=tmp;//慢指針--當(dāng)前節(jié)點的前一個節(jié)點，從哨兵衛(wèi)開始
struct ListNode*cur=head;//快指針遍歷鏈表的當(dāng)前節(jié)點，從頭結(jié)點開始
//遍歷整個鏈表
while(cur!=NULL)
{
if(cur->val==val)//如果當(dāng)前節(jié)點的值等于val的話，那么我們就跳過當(dāng)前節(jié)點
{
prev->next=cur->next;//當(dāng)前遍歷的節(jié)點的前一個節(jié)點的next將會直接指向當(dāng)前節(jié)點的下個節(jié)點
//就是說直接將當(dāng)前節(jié)點忽略掉了
}
else//當(dāng)前節(jié)點的值不等于val，那么我們繼續(xù)往后移動
{
//移動prev
prev=cur;
}
cur=cur->next;
}
//循環(huán)結(jié)束了，那么這個滿足條件的節(jié)點就刪除了
//重新定義頭結(jié)點，將哨兵衛(wèi)忽略就行了
struct ListNode*newHead=tmp->next;//用指針將頭節(jié)點進行定義
free(tmp);//釋放哨兵衛(wèi)
return newHead;//返回我們之前保存的頭結(jié)點的指針
}
1.4 代碼解析
我們先利用malloc動態(tài)申請一個節(jié)點賦值給tmp，這個tmp就是我們所說的哨兵位，用來占位子的 然后我們的tmp的next指針就指向我們原先的頭結(jié)點了 然后我們再創(chuàng)建兩個指針：
prev—慢指針，當(dāng)前節(jié)點的前一個節(jié)點，從哨兵位開始cur—當(dāng)前節(jié)點，從頭結(jié)點開始
說明：我們的這個哨兵位僅僅是一個空節(jié)點，并不存在實際的數(shù)據(jù)的，我們創(chuàng)建出來只是用來占位子的
然后我們就可以進行遍歷整個鏈表的操作了 遍歷的循環(huán)條件是我們的當(dāng)前節(jié)點cur不是空，就是只要到了尾節(jié)點我們就停下來了 我們在循環(huán)里面進行判斷，如果當(dāng)前節(jié)點的val滿足條件的話，我們讓這個節(jié)點的前一個節(jié)點指向這個節(jié)點的下一個節(jié)點，來達(dá)到間接刪除當(dāng)前的節(jié)點的作用 但是如果當(dāng)前節(jié)點不滿足的話我們就讓prev這個指針賦值為cur 然后在這個while循環(huán)的結(jié)束位置，我們就進行移動的操作，進行鏈表節(jié)點的遍歷操作 等循環(huán)結(jié)束了，我們這個鏈表中滿足條件的val就間接被刪除了 然后我們再重新定義頭結(jié)點 頭結(jié)點就是我們哨兵位的next指針指向的節(jié)點，這個時候我們的哨兵位的作用就發(fā)揮出來了 然后我們將哨兵位釋放掉就行了，這個題就結(jié)束了
2. 反轉(zhuǎn)鏈表
題目傳送門
2. 1題目說明
這是 LeetCode 第 206 題：反轉(zhuǎn)鏈表 的問題描述：
給定一個單鏈表的頭節(jié)點 head，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。
示例 1
輸入： head = [1,2,3,4,5]輸出： [5,4,3,2,1]
示例 2
輸入： head = [1,2]輸出： [2,1]
示例 3
輸入： head = []輸出： []
限制條件
鏈表中節(jié)點的數(shù)量范圍是 [0, 5000]。-5000 <= Node.val <= 5000
2.2 題目分析
逆轉(zhuǎn)鏈表顧名思義就是鏈表逆置 假設(shè)當(dāng)前鏈表是1->2->3->4->5 逆置過后就是這個樣子的5->4->3->2->1
那么我們怎么進行下面的操作呢？ 我們還是使用雙指針進行鏈表的遍歷，關(guān)于這個逆置的操作我們在遍歷的時候同時進行 同樣是定義兩個指針，然后在遍歷的時候?qū)?dāng)前的指向指向上一個節(jié)點，然后進行當(dāng)前節(jié)點的改變，改變相鄰兩個節(jié)點的指針，隨手遍歷結(jié)束，我們的尾節(jié)點就變成了頭結(jié)點，最后我們直接將頭結(jié)點進行返回就行了 請看下面代碼部分
2.3 代碼部分
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode*prev=NULL;//定義當(dāng)前節(jié)點的前一個節(jié)點
//因為反轉(zhuǎn)后原始鏈表的頭節(jié)點將成為新鏈表的尾節(jié)點，它的下一個節(jié)點應(yīng)該指向 NULL。
struct ListNode*cur=head;//用于遍歷鏈表，從頭結(jié)點開始
while(cur!=NULL)//遍歷鏈表
{
struct ListNode*nexttmp=cur->next;//保存當(dāng)前節(jié)點的下一個節(jié)點
//下面的兩個代碼就是對當(dāng)前節(jié)點和當(dāng)前節(jié)點的前面進行操作，進行指針逆轉(zhuǎn)操作
cur->next=prev;//當(dāng)前節(jié)點的指針反轉(zhuǎn)了，指向了前一個節(jié)點
prev=cur;//當(dāng)前節(jié)點變成了前一個節(jié)點了
cur=nexttmp;//將cur移動到下一個節(jié)點的位置
}
//出了循環(huán)之后這個逆轉(zhuǎn)操作就完成了
return prev;//反轉(zhuǎn)后的鏈表prev成為了新的頭節(jié)點了
}
2.4 代碼分析
我們先定義一個指針prev指向前一個節(jié)點，但是初始化我們設(shè)置為NULL,然后我們再定義一個指針cur指向當(dāng)前的頭節(jié)點head 然后我們使用while循環(huán)進行遍歷鏈表，結(jié)束條件是遍歷到尾節(jié)點就停止 我們在循環(huán)里面先定義一個指針nexttmp將當(dāng)前節(jié)點的下個節(jié)點進行保存的操作 然后下面就是我們?nèi)齻€節(jié)點直接的指向變換了 我們讓當(dāng)前節(jié)點cur的下一個節(jié)點的指針next指向我們的前一個節(jié)點prev,然后我們讓這個前一個節(jié)點prev變成我們的當(dāng)前節(jié)點cur進行下一組相鄰節(jié)點的逆置操作 然后我們讓當(dāng)前的cur變成我們當(dāng)時保存的下一個節(jié)點的指針，我們現(xiàn)在對這兩個節(jié)點進行逆置操作 隨著循環(huán)結(jié)束，我們的最后prev就變成了新的頭結(jié)點了 我們將這個節(jié)點返回操作就行了
柚子快報激活碼778899分享：輕觸節(jié)點，鏈表里的悄然邂逅
精彩內(nèi)容
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Wish海外心愿
