24. 两两交换链表中的节点

Problem: 24. 两两交换链表中的节点

错误

while(dummyHead->next != nullptr && dummyHead->next->next != nullptr)此处是cur

要记住，要交换后面两节点，必定得到两个节点的前面一个节点。

复杂度

• 时间复杂度:

$O(n)$

• 空间复杂度:

$O(1)$

Code

`

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr) return nullptr;
        // 当前节点和前一个节点和后一个节点
        ListNode* dummy = new ListNode(0),*pre = dummy,*cur = head;
        dummy->next = cur;
        while (cur != nullptr) {
            //next
            ListNode* next = cur->next;
            if(next == nullptr) break;
            // 保存next的next
            ListNode* nextNext = next->next;
            // 交换前后节点
            pre->next = next;
            next->next = cur;
            cur->next = nextNext;

            pre = cur;
            cur = nextNext;
        }
        return dummy->next;
    }
};

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; // 记录临时节点
            ListNode* tmp1 = cur->next->next->next; // 记录临时节点

            cur->next = cur->next->next;    // 步骤一
            cur->next->next = tmp;          // 步骤二
            cur->next->next->next = tmp1;   // 步骤三

            cur = cur->next->next; // cur移动两位，准备下一轮交换
        }
        return dummyHead->next;
    }
};