【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;
    }
};