往期部落格：
Leetcode1-兩數之和詳解
Leetcode2-兩數相加代碼詳解
Leetcode20-有效的括号詳解
Leetcode21-合并兩個有序連結清單詳解
Leetcode22-有效括号生成詳解
目錄
題目
示例
解析
疊代法
代碼
Python代碼
Java代碼
疊代法
代碼
Python代碼
Java代碼
題目
給你一個連結清單，兩兩交換其中相鄰的節點，并傳回交換後連結清單的頭節點。你必須在不修改節點内部的值的情況下完成本題（即，隻能進行節點交換）。
讓我們分析一下題目：
已知：一個連結清單
目的：交換相鄰兩節點
要求：傳回交換後的連結清單頭節點
示例
示例1
輸入：head = [1,2,3,4] 輸出：[2,1,4,3]
示例2
輸入：head = [] 輸出：[]
示例3
輸入：head = [1] 輸出：[1]
解析
疊代法
對于疊代法就是将連結清單從頭到尾進行周遊，将連結清單中的相鄰兩節點進行兩兩交換了，但是這裡要注意的時，在連結清單中我們變換的連結清單指針的指向，進而達到變換連結清單節點順序的效果。
對于下圖示例，将連結清單1—>2—>3—>1中相鄰兩節點進行兩兩交換，首先建立虛拟節點res，并将目前指針cur指向虛拟頭結點，head指針指向第一個節點“1”，next指針指向第二個節點“2”，tmp指針指向第三個節點“3”
首先是交換節點“1”和節點“2”的順序，斷開節點“res”與節點“1”的指針，并将指針指向節點“2”
斷開節點“2”與節點“3”的指針，并将節點“2”指向節點“1”
将節點“1”指向節點“3”
至此，已經完成了第一節點和第二節點的交換
再進行第二次疊代，交換第三節點和第四節點，但此時cur指向節點“2”，head指向節點“1”，next指向節點“3”，tmp指第四節點“1”，然後再進行如上操作
最終得到最後講過全部交換後的連結清單
代碼
Python代碼
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# 對于空連結清單隻有一個節點的連結清單，直接傳回原連結清單
if head == None or head.next == None:
return head
res = ListNode() # 建立虛拟頭結點
res.next = head # head指向第一個節點
cur = res # cur指向虛拟節點
while cur.next != None and cur.next.next != None:
nxt = head.next # nxt指向第二節點
tmp = nxt.next # tmp指向第三節點
cur.next = nxt # 虛拟頭節點指向第二節點
nxt.next = head # 第二節點指向第一節點
head.next = tmp # 第一節點指向第三節點
cur = head # 準備第二次疊代, cur第一節點
head = head.next # head指向第二節點
return res.next # 傳回交換後的連結清單，即虛拟頭結點後的所有節點
Java代碼
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode res = new ListNode(0);
res.next = head;
ListNode cur = res;
while(cur.next != null && cur.next.next != null){
ListNode next = head.next;
ListNode tmp = head.next.next;
cur.next = next;
next.next = head;
head.next = tmp;
cur = head;
head = head.next;
}
return res.next;
}
}
疊代法
将head指向第一節點“1”，将next指向第二節點“2”
将第一節點指向第三節點，同時第三第四節點進行遞歸，head指向第三節點，next指向第四節點
其中遞歸部分将第四節點指向第三節點
然後第二幾點指向第一節點
是以最終得到最後所有家電見後順序後的連結清單
代碼
Python代碼
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# 對于空連結清單隻有一個節點的連結清單，直接傳回原連結清單
if head == None or head.next == None:
return head
nxt = head.next
head.next = self.swapPairs(head.next.next)
nxt.next = head
return nxt
Java代碼
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode next = head.next;
head.next = swapPairs(head.next.next);
next.next = head;
return next;
}
}