# 24. Swap Nodes in Pairs

## [題目](https://leetcode.com/problems/swap-nodes-in-pairs/description/)

## 演算法

交換a,b兩點=>將指向a點的指標指向b點，將b點指向的指標給a點指向，b再指向a
1. 定義dummy，dummy->next指向頭
2. 定義prev指向dummy, current指向head
3. 當current != nullptr and current->next != nullptr:(要交換current與current->next)
    3.1 定義next指向current->next
    3.2 current->next指向next->next
    3.3 next->next指向current
    3.4 prev->next指向next
    3.5 prev指向current
    3.6 current指向current->next
4. head = dummy -> next
5. 刪除dummy，回傳head

## 演算法正確性證明
循環不變式：在迴圈開始前，除了dummy以外，current以前的節點都swap過了，prev->next會指向current

:::warning
老實說，這個演算法的正確性有點難證
:::
## 程式碼

/**
* 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) {
ListNode *dummy = new ListNode;
dummy -> next = head;
ListNode *prev = dummy, *current = head;
while (current != nullptr and current -> next != nullptr) {
ListNode *next = current -> next;
current -> next = next -> next;
prev -> next = next;
next -> next = current;
prev = current;
current = current -> next;
}
head = dummy -> next;
delete dummy;
return head;
}
};