題目描述
24.兩兩交換鏈表中的節點
給定一個鏈表，兩兩交換其中相鄰的節點，并回傳交換后的鏈表，
你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換，
示例：
給定 1->2->3->4, 你應該回傳 2->1->4->3.
題目決議
方法一：遞回
解題思路
遞回的解題思路在于把子問題交給下一層遞回函式處理，而本身只聚焦于本層次的問題，當你得到遞回函式回傳值時，默認為已經得到正確結果，只需要繼續處理當前層邏輯即可，
本題需要兩兩交換鏈表節點，所以頭節點 head 的下一個節點 next 必然就是新的頭節點 newHead ，然后通過遞回的方式交換 next 節點后面的鏈表，得到后續鏈表交換節點后直接賦值給頭節點 head 的next指標，處理 newHead 和 head 的關聯，得到交換后的鏈表，
代碼示例
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)，在遞回時使用額外堆疊空間，
方法二：迭代
解題思路
迭代的方式大家都比較熟悉，從鏈表頭節點開始遍歷然后兩兩交換節點，在交換節點的程序中，需要注意就是鏈表遍歷到什么位置了，兩兩節點交換完成后是否還能繼續向后遍歷，
迭代解法中通過 prev 和 curr 指標用來記錄鏈表當前遍歷位置，并且在兩兩節點交換完成后 prev 和 curr 指標向后移動繼續進行節點交換，直到鏈表末尾，
代碼示例
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) {
// 記錄當前節點的next節點
ListNode next = curr.next;
// 交換節點
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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65514.html
標籤：其他
上一篇：原碼，反碼與補碼