24. 兩兩交換鏈表中的節(jié)點(diǎn)(遞歸版)
24. 兩兩交換鏈表中的節(jié)點(diǎn)
難度中等1780
給你一個(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
/**
?*?Definition?for?singly-linked?list.
?*?struct?ListNode?{
?*?????int?val;
?*?????struct?ListNode?*next;
?*?};
?*/
struct?ListNode*?swapPairs(struct?ListNode*?head){
???if(head==NULL||head->next==NULL)return?head;
???struct?ListNode*?second=head->next;
????head->next?=?swapPairs(second->next);
????second->next?=?head;
???return?second;
}
遞歸思路：
想清楚要循環(huán)執(zhí)行的代碼：需要循環(huán)執(zhí)行的是讓后一個(gè)指向前一個(gè)，前一個(gè)指向的是下一組需要調(diào)換的結(jié)點(diǎn)的看后面一個(gè)。
想清楚要返回的數(shù)據(jù)：需要返回每組結(jié)點(diǎn)的后一個(gè)，因?yàn)槊恳唤M結(jié)點(diǎn)的前一個(gè)是要每次都是要指向下一組結(jié)點(diǎn)的后一個(gè)的
想清楚結(jié)束的條件：當(dāng)節(jié)點(diǎn)數(shù)是雙數(shù)時(shí)，當(dāng)頭節(jié)點(diǎn)為NULL時(shí)返回當(dāng)前頭節(jié)點(diǎn)（NULL），當(dāng)頭節(jié)點(diǎn)為單數(shù)時(shí)，當(dāng)頭節(jié)點(diǎn)的下一個(gè)為NULL時(shí)返回當(dāng)前頭節(jié)點(diǎn)。
