題目描述
給定一個鏈表，兩兩交換其中相鄰的節(jié)點掐松，并返回交換后的鏈表附帽。
你不能只是單純的改變節(jié)點內(nèi)部的值，而是需要實際的進行節(jié)點交換馆衔。
示例：
給定 1->2->3->4, 你應該返回 2->1->4->3.
題目解析
方法一：遞歸
解題思路
遞歸的解題思路在于把子問題交給下一層遞歸函數(shù)處理瘟判，而本身只聚焦于本層次的問題怨绣，當你得到遞歸函數(shù)返回值時，默認為已經(jīng)得到正確結(jié)果拷获，只需要繼續(xù)處理當前層邏輯即可篮撑。
本題需要兩兩交換鏈表節(jié)點，所以頭節(jié)點 head 的下一個節(jié)點 next 必然就是新的頭節(jié)點 newHead 匆瓜，然后通過遞歸的方式交換 next 節(jié)點后面的鏈表赢笨，得到后續(xù)鏈表交換節(jié)點后直接賦值給頭節(jié)點 head 的next指針，處理 newHead 和 head 的關聯(lián)驮吱，得到交換后的鏈表茧妒。
代碼示例
Java：
/**
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode swapPairs(ListNode head) {
// terminator
if (head == null || head.next == null) {
return head;
}
// recursion
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
// process data
newHead.next = head;
return newHead;
}
復雜度分析
時間復雜度：O(n)
空間復雜度：O(n)，在遞歸時使用額外椬蠖空間桐筏。
方法二：迭代
解題思路
迭代的方式大家都比較熟悉，從鏈表頭節(jié)點開始遍歷然后兩兩交換節(jié)點拇砰。在交換節(jié)點的過程中梅忌，需要注意就是鏈表遍歷到什么位置了，兩兩節(jié)點交換完成后是否還能繼續(xù)向后遍歷除破。
迭代解法中通過 prev 和 curr 指針用來記錄鏈表當前遍歷位置牧氮，并且在兩兩節(jié)點交換完成后 prev 和 curr 指針向后移動繼續(xù)進行節(jié)點交換，直到鏈表末尾瑰枫。
代碼示例
Java：
/**
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode swapPairs(ListNode head) {
ListNode newHead = new ListNode(0);
newHead.next = head;
ListNode prev = newHead, curr = head;
while(curr != null && curr.next != null) {
// 記錄當前節(jié)點的next節(jié)點
ListNode next = curr.next;
// 交換節(jié)點
curr.next = curr.next.next;
next.next = curr;
prev.next = next;
// prev踱葛，curr指針后移
prev = curr;
curr = curr.next;
}
return newHead.next;
}
復雜度分析
時間復雜度：O(n)
空間復雜度：O(1)
