24. 兩兩交換鏈表中的節點 - 力扣（LeetCode）

題解：

- 迭代

首先是直接遍歷的做法，這里注意調整指針指向的順序。

/*** 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 * dummyHead = new ListNode(0);dummyHead -> next = head;ListNode * tmp = dummyHead;ListNode*first, *second; // 反轉前后用到的臨時節點while(tmp->next!=nullptr && tmp->next->next!=nullptr){first = tmp->next;second = tmp->next->next;// 先調整tmp，再調整 first，再調整 secondtmp -> next = second;first -> next = second -> next;second -> next = first;tmp = first;}ListNode * ans = dummyHead -> next;delete dummyHead;return ans;}
};

- 遞歸

遞歸的本質在于直接處理最小子集。

/*** 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 == nullptr || head -> next == nullptr){return head;}ListNode *newHead = head -> next;head -> next = swapPairs(newHead -> next);newHead -> next = head;return newHead;}
};