目錄鏈接：http://www.itdecent.cn/p/9c0ada9e0ede
兩兩交換其中相鄰的節(jié)點(diǎn)
LeetCode 24. 兩兩交換鏈表中的節(jié)點(diǎn)(Swap Nodes in Pairs)
給定一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后的鏈表。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。
示例:
給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.
切題
一、Clarification
目標(biāo)明確兩兩交換鏈表中的節(jié)點(diǎn)，無特別需要注意的邊界但需常規(guī)關(guān)注下空鏈表和只有一個(gè)元素的鏈表
二、Possible solutions
1、迭代
在邊界內(nèi)同時(shí)取出2個(gè)節(jié)點(diǎn)并交換，然后向下移動2位
使用哨兵簡化處理，空鏈表，一個(gè)元素的鏈表
2、遞歸
遞歸終止條件 head 和 head.next 為None
每層遞歸交換當(dāng)前兩節(jié)點(diǎn)，并返回 交換后兩個(gè)節(jié)點(diǎn)中的前一個(gè)節(jié)點(diǎn)
Python3 實(shí)現(xiàn)
迭代實(shí)現(xiàn)
兩兩交換其中相鄰的節(jié)點(diǎn)(Swap Nodes in Pairs) Py3 迭代實(shí)現(xiàn)
#@author:leacoder
#@des: 循環(huán)實(shí)現(xiàn) 多元賦值
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
pre = ListNode(None) # 哨兵
retult,pre.next =pre, head
while pre.next and pre.next.next:
a = pre.next
b = pre.next.next # 記錄 要交換的兩節(jié)點(diǎn)
pre.next,b.next,a.next,= b,a,b.next # 2個(gè)節(jié)點(diǎn)交換,注意哨兵的next改變了
pre = a # 向下移動2位
return retult.next
遞歸實(shí)現(xiàn)
#@author:leacoder
#@des: 遞歸實(shí)現(xiàn) 多元賦值
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
resultmp = self.swapPairs(head.next.next) # 下移兩位 返回 值為兩兩交換后 兩個(gè)節(jié)點(diǎn)中的前一個(gè)節(jié)點(diǎn)
# 交換 當(dāng)前兩節(jié)點(diǎn)
A, B = head, head.next # 當(dāng)前兩節(jié)點(diǎn)
A.next, B.next = resultmp,A # 交換
return B # 返回 兩兩交換后 兩個(gè)節(jié)點(diǎn)中的前一個(gè)節(jié)點(diǎn)
C++實(shí)現(xiàn)
1、迭代實(shí)現(xiàn) C++
兩兩交換其中相鄰的節(jié)點(diǎn)(Swap Nodes in Pairs) C++ 迭代實(shí)現(xiàn)
* @author:leacoder
* @des: 迭代實(shí)現(xiàn) 兩兩交換鏈表中的節(jié)點(diǎn)
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
/*在頭節(jié)點(diǎn)前 新建一節(jié)點(diǎn)，其next指向head。好處 將[]\[1]這種特殊情況能夠統(tǒng)一處理*/
ListNode *virtualnode = new ListNode(0);
virtualnode->next = head;
ListNode *node = virtualnode;//存儲新的開始節(jié)點(diǎn)
while(head&&head->next){
ListNode *tmp = head->next;//不變的
head->next = tmp->next;
tmp->next = head;//交換
node->next = tmp;
node = head;
head = node->next;//下移
}
return virtualnode->next;
}
};
2、遞歸實(shí)現(xiàn) C++
兩兩交換其中相鄰的節(jié)點(diǎn)(Swap Nodes in Pairs) C++ 遞歸實(shí)現(xiàn)
/**
* @author:leacoder
* @des: 遞歸實(shí)現(xiàn) 兩兩交換鏈表中的節(jié)點(diǎn)
*/
class Solution {
public:
//每兩個(gè)節(jié)點(diǎn)為一組 反轉(zhuǎn)前的前節(jié)點(diǎn)（反轉(zhuǎn)后的 后節(jié)點(diǎn)）、反轉(zhuǎn)前的后節(jié)點(diǎn)（反轉(zhuǎn)后的 前節(jié)點(diǎn)）
//下一組 為 反轉(zhuǎn)前的后節(jié)點(diǎn)（反轉(zhuǎn)后的 前節(jié)點(diǎn)）的 next 以及 next.next
ListNode* swapPairs(ListNode* head) { //入?yún)?反轉(zhuǎn)前的前節(jié)點(diǎn)（反轉(zhuǎn)后的 后節(jié)點(diǎn)）
////傳入的參數(shù)的合法性，遞歸的終止條件
if (NULL==head || NULL==head->next)
return head;
ListNode *res = head->next; //記錄 反轉(zhuǎn)前的后節(jié)點(diǎn)（反轉(zhuǎn)后的 前節(jié)點(diǎn)）
head->next = swapPairs(res->next); //更新 反轉(zhuǎn)后的 后節(jié)點(diǎn) 的next 為下一組 反轉(zhuǎn)后的 前節(jié)點(diǎn) （入?yún)榉崔D(zhuǎn)前的后節(jié)點(diǎn)的next 即為下一組的 反轉(zhuǎn)前的前節(jié)點(diǎn)（反轉(zhuǎn)后的 后節(jié)點(diǎn)）
res->next = head; //更新 反轉(zhuǎn)后的 前節(jié)點(diǎn)的next 為 反轉(zhuǎn)前 的 前節(jié)點(diǎn)
return res;
}
};
以【A B C D】為例，那么可分為2組【A B】【C D】遞歸到最后一層非head->next = NULL那層， ListNode* swapPairs(ListNode* head)｛｝中head為C，head->next為D。
那么就有：
·【C D】組 此時(shí) head 為 C 交換前
ListNode *res = head->next; //D
head->next = swapPairs(res->next); //C->next = D->next=NULL 入?yún)镈->next NULL值跳出遞歸 返回入?yún)?
res->next = head; //D->next = C
return res; //D
此時(shí)結(jié)果為 【A B D C】
·【A B】組 此時(shí) head 為 A 交換前
ListNode *res = head->next; //B
head->next = D //上次迭代返回值 swapPairs(C)
res->next = head; //B->next = A
return res; //B
此時(shí)結(jié)果為 【B A D C】
其他情況可同上分析
Java實(shí)現(xiàn)
Java實(shí)現(xiàn)邏輯上與C++無區(qū)別
1、迭代實(shí)現(xiàn) Java
兩兩交換其中相鄰的節(jié)點(diǎn)(Swap Nodes in Pairs) Java 迭代實(shí)現(xiàn)
2、遞歸實(shí)現(xiàn) Java
兩兩交換其中相鄰的節(jié)點(diǎn)(Swap Nodes in Pairs) Java 遞歸實(shí)現(xiàn)
GitHub鏈接：
https://github.com/lichangke/LeetCode
知乎個(gè)人首頁：
https://www.zhihu.com/people/lichangke/
簡書個(gè)人首頁：
http://www.itdecent.cn/u/3e95c7555dc7
個(gè)人Blog:
https://lichangke.github.io/
歡迎大家來一起交流學(xué)習(xí)
