24. 兩兩交換鏈表中的節(jié)點(diǎn)
24. 兩兩交換鏈表中的節(jié)點(diǎn)
難度中等1779
給你一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后鏈表的頭節(jié)點(diǎn)。你必須在不修改節(jié)點(diǎn)內(nèi)部的值的情況下完成本題（即，只能進(jìn)行節(jié)點(diǎn)交換）。
?
示例 1：
輸入：head = [1,2,3,4]輸出：[2,1,4,3]
示例 2：
輸入：head = []
輸出：[]
示例 3：
輸入：head = [1]
輸出：[1]
?
提示：
鏈表中節(jié)點(diǎn)的數(shù)目在范圍 [0, 100] 內(nèi)
0 <= Node.val <= 100
通過(guò)次數(shù)605,324提交次數(shù)849,278
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/swap-nodes-in-pairs
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
第一種錯(cuò)法：
/**
?*?Definition?for?singly-linked?list.
?*?struct?ListNode?{
?*?????int?val;
?*?????struct?ListNode?*next;
?*?};
?*/
struct?ListNode*?swapPairs(struct?ListNode*?head){
????if(!head)return?head;
????if(!head->next)return?head;
????struct?ListNode?*first;
????struct?ListNode?*second;
????struct?ListNode?*pre;
????struct?ListNode?*ans?=?head->next;
????pre?=?head;
????while(pre){
????????first?=?pre;
????????second?=?pre->next;
????????pre?=?second->next;
????????second->next?=?first;
????????if(!pre)?first->next?=?NULL;
????????else?first->next?=?pre->next;
????}
????return?ans;
}
這個(gè)代碼問(wèn)題出在它沒(méi)辦法判斷單數(shù)結(jié)點(diǎn)的情況下，second為空的狀態(tài)。操作了空指針。
我自己寫(xiě)的代碼都沒(méi)有考慮到結(jié)點(diǎn)單復(fù)數(shù)的問(wèn)題，只是一味的想特判，但是還是沒(méi)用。一開(kāi)始時(shí)想到了要做一個(gè)虛擬頭節(jié)點(diǎn)但是沒(méi)去做。循環(huán)的基本邏輯沒(méi)錯(cuò)，但是總是會(huì)操作空指針。
下次要注意一個(gè)指針被賦予另一個(gè)結(jié)點(diǎn)的時(shí)候這個(gè)結(jié)點(diǎn)會(huì)不會(huì)有可能為空，若有可能就不能對(duì)它取next否則會(huì)操作空指針。
第一種對(duì)法：
/**
?*?Definition?for?singly-linked?list.
?*?struct?ListNode?{
?*?????int?val;
?*?????struct?ListNode?*next;
?*?};
?*/
struct?ListNode*?swapPairs(struct?ListNode*?head){
????struct?ListNode*?vithead?=?(struct?ListNode*)malloc(sizeof(struct?ListNode));
????vithead->next?=?head;
????struct?ListNode*?cur?=?vithead;
????while(cur->next&&cur->next->next){
????????struct?ListNode*?tmp1?=?cur->next;
????????cur->next?=?cur->next->next;
????????struct?ListNode*?tmp2?=?cur->next->next;
????????cur->next->next?=?tmp1;
????????tmp1->next?=?tmp2;
????????cur?=?tmp1;
????}
????return?vithead->next;
}
要注意的點(diǎn)：
創(chuàng)建虛擬頭節(jié)點(diǎn)，注意c語(yǔ)言要把struct 寫(xiě)在前面
循環(huán)判斷條件，讓cur能遍歷到全部之后返回頭指針，就是說(shuō)如果最后cur的下一個(gè)結(jié)點(diǎn)（節(jié)點(diǎn)數(shù)為奇數(shù)）或cur的下一個(gè)的下一個(gè)結(jié)點(diǎn)（節(jié)點(diǎn)數(shù)為偶數(shù)）為空時(shí)退出
循環(huán)條件必須cur->next寫(xiě)在前面不然如果cur->next為空那么cur->next->next就是操作空指針了
循環(huán)里面的內(nèi)容最好畫(huà)圖來(lái)解決，不然很容易出現(xiàn)死循環(huán)
cur始終要指向需要交換的兩個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)那里
