這次來寫一下 LeetCode 的第 24 題须蜗，兩兩交換鏈表中的節(jié)點奇瘦。
題目描述
題目直接從 LeetCode 上截圖過來忧陪，題目如下：
上面的題就是 兩兩交換鏈表中的節(jié)點 題目的截圖鹦牛，同時 LeetCode 給出了一個函數(shù)的定義羹幸，然后要求實現(xiàn)鏈表兩兩交換的函數(shù)體。函數(shù)定義如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head){
}
從定義上看赁遗，是一個單鏈表署辉，單鏈表只能順著節(jié)點的指針依次找下去，而不能往回找岩四。
問題分析
這個題目看似簡單哭尝，其實還是有幾個坑在里面的。聽我慢慢道來剖煌。
先來看看材鹦，鏈表最初的情況，如下圖：
最初鏈表的頭指向第一個節(jié)點耕姊，我們首先要交換的是第一個節(jié)點和第二個節(jié)點桶唐，根據(jù)指針來看，只要讓第一個節(jié)點的 next 指向第三個節(jié)點茉兰，然后讓第二個節(jié)點的 next 指向第一個節(jié)點就可以了尤泽。在交換之前，首先要有一個指針（pre）指向第一個節(jié)點规脸、還要有一個指針（cur）指向第二個節(jié)點坯约，當然再準備一個指針（new）指向第三個節(jié)點。有了這些指針莫鸭，就可以完成我們的交換了闹丐，如下圖：
當交換完成以后，就接著移動這三個指針被因，進行下一次的交換卿拴。這樣就構(gòu)成了一個循環(huán)，怎么來判斷是否循環(huán)梨与？讓 new = head堕花，當 new 為 NULL 或者 new->next 為 NULL 的時候，就說明沒有節(jié)點或者只剩一個節(jié)點了蛋欣，就不用再交換了，這樣循環(huán)就結(jié)束了如贷。
以上看似完成了陷虎，其實還是有一個問題，我們接著推第二步交換試試杠袱。如下圖：
開始第二輪交換的時候尚猿，指針的位置是這樣的，然后按照前面的指針交換的方式進行交換楣富。圖下圖：
交換完后的鏈表成了這個樣子凿掂，但是仔細觀察，不知道是否觀察出了問題。我們的 4 號節(jié)點沒有辦法遍歷到了庄萎。因為 1 號節(jié)點的指針仍然指向著 3 號節(jié)點踪少，而經(jīng)過交換，要把 4 號節(jié)點放到 3 號節(jié)點的前面糠涛。那么援奢，也就是說，除了要完成 3 號節(jié)點和 4 號節(jié)點的交換忍捡，還要修正 1 號節(jié)點中 next 的指向集漾。而此時，我們已經(jīng)沒有指針指向 1 號節(jié)點了砸脊。所以具篇，我們增加一個指針 tmp 來指向 pre 指針就可以了，以后通過 tmp 指針的 next 來修正即可凌埂。修正后如下圖：
當以后兩個節(jié)點交換完成后驱显，將 pre 指針賦值給 tmp 指針即可。
這樣看似完成了侨舆，那么還有問題么秒紧？問題還是有的，我們的 head 指針一直指向的是 1 號節(jié)點挨下，但是實際的鏈表頭節(jié)點已經(jīng)是 2 號節(jié)點了熔恢。當函數(shù)執(zhí)行完成時，需要返回新的鏈表頭節(jié)點臭笆，要怎么返回呢叙淌？我這里又增加了一個新的指針 result 來記錄新的頭節(jié)點，當循環(huán)完成以后愁铺，直接返回 result 就可以了鹰霍。
上面的步驟就算完成了，幾個問題其實都是我在寫代碼的時候遇到的茵乱。雖然步驟是完成了茂洒，但是我覺得我的代碼應(yīng)該還是有簡化的空間的。暫時沒有再去考慮了瓶竭。
代碼實現(xiàn)
上面說了那么多督勺，其實代碼反倒不是很復雜。代碼如下：
/**
* 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é)點智哀，只要大于等于兩個節(jié)點，那么新的鏈表頭都是第二個節(jié)點
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;
// 為了修正荧恍，需要保留當前交換的前一個節(jié)點
tmp = pre;
}
return result;
}
注釋是我剛剛加上去的瓷叫，其實自己整理了一遍，發(fā)現(xiàn)思路比當時寫的時候清晰了許多。整理和總結(jié)真的是挺重要的摹菠。
提交結(jié)果
在寫完 swapPairs 函數(shù)體后盒卸，點擊右下角的 “執(zhí)行代碼”，然后觀察 “輸出” 和 “預期結(jié)果” 是否一致辨嗽，一致的話就點擊 “提交” 按鈕世落。點擊 “提交” 按鈕后，系統(tǒng)會使用更多的測試用例來測試我們寫的函數(shù)體糟需，如果所有的測試用例都通過了屉佳，那么就會給出 “通過” 的字樣，如果沒有通過洲押，會給出失敗的那一組測試用例武花，我們繼續(xù)修改代碼。我們以上代碼 “提交” 以后的截圖如下：
我覺得在內(nèi)存消耗上應(yīng)該可以更小一些杈帐，我為了截這個圖体箕，重新提交了代碼，在提交代碼前還修改了幾行代碼挑童，內(nèi)存消耗也由 5.5 MB 變?yōu)榱?5.4 MB累铅，通過梳理自己還是能找到改進空間，給自己點個贊站叼。
