No. 24 - Swap Nodes in Pairs
====
---
## [LeetCode 24 -- Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
### 題目描述
Given a linked list, swap every two adjacent nodes and return its head.
For example:
Before swap,
```graphviz
digraph {
node [shape = circle];
rankdir=LR
2, 4 [color=lightblue,style=filled]
1->2->3->4
}
```
After swap,
```graphviz
digraph {
node [shape = circle];
rankdir=LR
2, 4 [color=lightblue,style=filled]
2->1->4->3
}
```
Example 1.
```
Input: head = [1,2,3,4]
Output: [2,1,4,3]
```
Example 2.
```
Input: head = [1,2,3]
Output: [2,1,3]
```
---
### 解法
本題目的是將 linked list 上每相鄰的兩個 nodes 相互交換。
我們以下面這個 linked list 為例，這個 linked list 從 node 1 到 6 兩兩進行相互交換，也就是說淺藍色的 node 會跟其左邊的白色 node 互換。
```graphviz
digraph linkedList{
node [shape = circle];
rankdir=LR;
2, 4, 6 [color=lightblue,style=filled];
1 -> 2;
2 -> 3;
3 -> 4;
4 -> 5;
5 -> 6;
}
```
首先，我們先講解相鄰 nodes 互換的作法。
當我們將兩個 nodes 互換時，它們所指向的下個 node 也必須改變。以下面的例子來說，原本 node 2 的下個 node 是 node 3 而 node 1 的下個 node 2，但經過互換後 node 2 的下個 node 改成 node 1 而 node 1 的下個 node 為 node 3。
```graphviz
digraph linkedList{
label="互換前"
node [shape = circle];
rankdir=LR;
2[color=lightblue,style=filled];
1 -> 2;
2 -> 3;
}
```
```graphviz
digraph linkedList{
label="互換後"
node [shape = circle];
rankdir=LR;
2[color=lightblue,style=filled];
2 -> 1;
1 -> 3;
}
```
1. 我們首先知道當前的 node 指標是在 node 1 (紅色代表當前指標)
```graphviz
digraph linkedList{
node [shape = circle];
rankdir=LR;
1 [color=red,style=filled];
1 -> 2;
2 -> 3;
}
```
2. 接著我們需要宣告一個新的 node 來記錄當前的 node 指向的下一個 node (用綠色代表)。
```graphviz
digraph linkedList{
node [shape = circle];
rankdir=LR;
2 [color=green,style=filled];
1 [color=red,style=filled];
1 -> 2;
2 -> 3;
}
```
3. 最後只要將當前 node (紅色 node) 指向下一個 node 的指標指向下一個 node (綠色 node) 的下一個 node (node 3)，再將下一個 node (綠色 node) 指向下一個 node 的指標指回當前 node (紅色 node) 即可完成互換。
```graphviz
digraph linkedList{
node [shape = circle];
rankdir=LR;
2 [color=green,style=filled];
1 [color=red,style=filled];
2 -> 1;
1 -> 3;
}
```
node 互換的程式如下， head 為給定的當前 node 指標 (紅色 node)，我們要另外宣告一個 `node` 儲存當前 node 的下一個 node (綠色 node)。
```CPP=
ListNode *node = head->next;
head->next = node->next;
node->next = head;
return node;
```
而題目是要我們將整個 linked list 的 node 都兩兩互換，我們可以用前面講解的互換方法搭配遞迴的概念來實現。
我們仍用前面 node 1 到 node 6 的 linked list 範例來講解。
相較於從頭開始互換，用遞迴的概念來思考題目的話，它會像是從最後面開始互換。也就是說如下面的圖，node 3, 4 互換前 node 5, 6 會先互換好，並且 node 4 指向的下一個 node 是 node 5, 6 互換完的結果。
```graphviz
digraph linkedList{
subgraph cluster_0 {
node [shape = circle];
rankdir=LR;
color=red;
6 [color=lightblue,style=filled];
6->5;
}
node [shape = circle];
rankdir=LR;
2,4,6 [color=lightblue,style=filled];
1 -> 2;
2 -> 3;
3 -> 4;
4 -> 6;
}
```
依此類推，最前面的 node 1, 2 要互換時，後面的 node 3-6 也已經互換好了。我們可以把 node 2 所指向的下一個 node 看成是另外一組要做互換的 linked list 的開頭，而這個子 linked list 也透過一樣的方法進行互換，透過遞迴的方式來把整個 linked list 互換完成。
```graphviz
digraph linkedList{
node [shape = circle];
rankdir=LR;
2 [color=lightblue,style=filled];
1 -> 2;
2 -> sub_linked_list
}
```
整個 linked list 互換的程式如下，我們可以看到第 16-19 行就是前面講解 nodes 互換的做法，只是在第 17 行 `head` node 要跟下一個 node 互換需要改變指向下一個 node 的指標時，它所指的就像上圖的 `sub_linked_list`，是一個被 `swapPairs()` 互換完成的子 linked list。
另外，由於是兩兩 nodes 進行互換，當 nodes 是奇數的時候會有 node 落單不用互換。所以遞迴停止的條件不只是看當前 node 存不存在，還要看下一個 node 存不存在需不需要互換，這就是第 14-15 行判斷遞迴終止的條件。
```CPP=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next)
return head;
ListNode *node = head->next;
head->next = swapPair(node->next);
node->next = head
return node;
}
};
```
### 複雜度分析
在分析時間複雜度前，因為我們是用遞迴的方法，我們可以先列出遞迴關係式:$$T(N)=T(N-2)+O(1)$$這個遞迴關係式還滿簡單的，只需將其展開我們可得出其時間複雜度為 $O(N)$。
由於我們需要遞迴呼叫 `swapPairs` 函式，所以需要呼叫堆疊 (call stack) 來儲存每一次遞迴的函式，而此函式只會宣告固定的指標，所以需要 $O(N)$ 的空間複雜度。
:::info
另外也可用迭代的方式達成互換，若是用迭代的方式則空間複雜度為 $O(1)$，因為不需要呼叫堆疊來儲存遞迴的函式。
:::
Sign in with Wallet
Connect another wallet