這次來(lái)寫(xiě)一下 LeetCode 的第 24 題，兩兩交換鏈表中的節(jié)點(diǎn)。
題目描述
題目直接從 LeetCode 上截圖過(guò)來(lái)，題目如下：
上面的題就是 兩兩交換鏈表中的節(jié)點(diǎn) 題目的截圖，同時(shí) LeetCode 給出了一個(gè)函數(shù)的定義，然后要求實(shí)現(xiàn)鏈表兩兩交換的函數(shù)體。函數(shù)定義如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head){
}
從定義上看，是一個(gè)單鏈表，單鏈表只能順著節(jié)點(diǎn)的指針依次找下去，而不能往回找。
問(wèn)題分析
這個(gè)題目看似簡(jiǎn)單，其實(shí)還是有幾個(gè)坑在里面的。聽(tīng)我慢慢道來(lái)。
先來(lái)看看，鏈表最初的情況，如下圖：
最初鏈表的頭指向第一個(gè)節(jié)點(diǎn)，我們首先要交換的是第一個(gè)節(jié)點(diǎn)和第二個(gè)節(jié)點(diǎn)，根據(jù)指針來(lái)看，只要讓第一個(gè)節(jié)點(diǎn)的 next 指向第三個(gè)節(jié)點(diǎn)，然后讓第二個(gè)節(jié)點(diǎn)的 next 指向第一個(gè)節(jié)點(diǎn)就可以了。在交換之前，首先要有一個(gè)指針（pre）指向第一個(gè)節(jié)點(diǎn)、還要有一個(gè)指針（cur）指向第二個(gè)節(jié)點(diǎn)，當(dāng)然再準(zhǔn)備一個(gè)指針（new）指向第三個(gè)節(jié)點(diǎn)。有了這些指針，就可以完成我們的交換了，如下圖：
當(dāng)交換完成以后，就接著移動(dòng)這三個(gè)指針，進(jìn)行下一次的交換。這樣就構(gòu)成了一個(gè)循環(huán)，怎么來(lái)判斷是否循環(huán)？讓 new = head，當(dāng) new 為 NULL 或者 new->next 為 NULL 的時(shí)候，就說(shuō)明沒(méi)有節(jié)點(diǎn)或者只剩一個(gè)節(jié)點(diǎn)了，就不用再交換了，這樣循環(huán)就結(jié)束了。
以上看似完成了，其實(shí)還是有一個(gè)問(wèn)題，我們接著推第二步交換試試。如下圖：
開(kāi)始第二輪交換的時(shí)候，指針的位置是這樣的，然后按照前面的指針交換的方式進(jìn)行交換。圖下圖：
交換完后的鏈表成了這個(gè)樣子，但是仔細(xì)觀(guān)察，不知道是否觀(guān)察出了問(wèn)題。我們的 4 號(hào)節(jié)點(diǎn)沒(méi)有辦法遍歷到了。因?yàn)?1 號(hào)節(jié)點(diǎn)的指針仍然指向著 3 號(hào)節(jié)點(diǎn)，而經(jīng)過(guò)交換，要把 4 號(hào)節(jié)點(diǎn)放到 3 號(hào)節(jié)點(diǎn)的前面。那么，也就是說(shuō)，除了要完成 3 號(hào)節(jié)點(diǎn)和 4 號(hào)節(jié)點(diǎn)的交換，還要修正 1 號(hào)節(jié)點(diǎn)中 next 的指向。而此時(shí)，我們已經(jīng)沒(méi)有指針指向 1 號(hào)節(jié)點(diǎn)了。所以，我們?cè)黾右粋€(gè)指針 tmp 來(lái)指向 pre 指針就可以了，以后通過(guò) tmp 指針的 next 來(lái)修正即可。修正后如下圖：
當(dāng)以后兩個(gè)節(jié)點(diǎn)交換完成后，將 pre 指針賦值給 tmp 指針即可。
這樣看似完成了，那么還有問(wèn)題么？問(wèn)題還是有的，我們的 head 指針一直指向的是 1 號(hào)節(jié)點(diǎn)，但是實(shí)際的鏈表頭節(jié)點(diǎn)已經(jīng)是 2 號(hào)節(jié)點(diǎn)了。當(dāng)函數(shù)執(zhí)行完成時(shí)，需要返回新的鏈表頭節(jié)點(diǎn)，要怎么返回呢？我這里又增加了一個(gè)新的指針 result 來(lái)記錄新的頭節(jié)點(diǎn)，當(dāng)循環(huán)完成以后，直接返回 result 就可以了。
上面的步驟就算完成了，幾個(gè)問(wèn)題其實(shí)都是我在寫(xiě)代碼的時(shí)候遇到的。雖然步驟是完成了，但是我覺(jué)得我的代碼應(yīng)該還是有簡(jiǎn)化的空間的。暫時(shí)沒(méi)有再去考慮了。
代碼實(shí)現(xiàn)
上面說(shuō)了那么多，其實(shí)代碼反倒不是很復(fù)雜。代碼如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head){
struct ListNode *new = head;
struct ListNode *pre = NULL;
struct ListNode *cur = NULL;
// 如果鏈表本身就是空的，那么就直接返回好了
if (head == NULL) {
return head;
}
// 不管鏈表有多少節(jié)點(diǎn)，只要大于等于兩個(gè)節(jié)點(diǎn)，那么新的鏈表頭都是第二個(gè)節(jié)點(diǎn)
struct ListNode *result = head;
if (head->next != NULL) {
result = head->next;
}
struct ListNode *tmp = NULL;
while (new != NULL && new->next != NULL) {
// 設(shè)置 pre 和 cur 的位置
pre = new;
cur = new->next;
new = new->next->next;
// 交換
pre->next = cur->next;
cur->next = pre;
// 這就是在第二次以及以后交換中要修正的部分
if (tmp != NULL) tmp->next = cur;
// 為了修正，需要保留當(dāng)前交換的前一個(gè)節(jié)點(diǎn)
tmp = pre;
}
return result;
}
注釋是我剛剛加上去的，其實(shí)自己整理了一遍，發(fā)現(xiàn)思路比當(dāng)時(shí)寫(xiě)的時(shí)候清晰了許多。整理和總結(jié)真的是挺重要的。
提交結(jié)果
在寫(xiě)完 swapPairs 函數(shù)體后，點(diǎn)擊右下角的 “執(zhí)行代碼”，然后觀(guān)察 “輸出” 和 “預(yù)期結(jié)果” 是否一致，一致的話(huà)就點(diǎn)擊 “提交” 按鈕。點(diǎn)擊 “提交” 按鈕后，系統(tǒng)會(huì)使用更多的測(cè)試用例來(lái)測(cè)試我們寫(xiě)的函數(shù)體，如果所有的測(cè)試用例都通過(guò)了，那么就會(huì)給出 “通過(guò)” 的字樣，如果沒(méi)有通過(guò)，會(huì)給出失敗的那一組測(cè)試用例，我們繼續(xù)修改代碼。我們以上代碼 “提交” 以后的截圖如下：
我覺(jué)得在內(nèi)存消耗上應(yīng)該可以更小一些，我為了截這個(gè)圖，重新提交了代碼，在提交代碼前還修改了幾行代碼，內(nèi)存消耗也由 5.5 MB 變?yōu)榱?5.4 MB，通過(guò)梳理自己還是能找到改進(jìn)空間，給自己點(diǎn)個(gè)贊。
