【leetcode100-30】【链表】两两交换链表节点

【题干】

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

【思路】

• 先说递归的，退出条件很明显，当剩余节点不足两个的时候退出递归，条件可以写为tail->next&&tail->next->next，短路运算也保证了不会进行nullptr的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;}
};

迭代

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* temp = dummyHead;while (temp->next != nullptr && temp->next->next != nullptr) {ListNode* node1 = temp->next;ListNode* node2 = temp->next->next;temp->next = node2;node1->next = node2->next;node2->next = node1;temp = node1;}ListNode* ans = dummyHead->next;delete dummyHead;return ans;}
};