没限制空间

/**
 * 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 dummy1, dummy2;
        ListNode* head1 = &dummy1;
        ListNode* head2 = &dummy2;
        ListNode* temp = head;
        int cnt = 1;

        // 拆分链表为奇数位置和偶数位置节点链表
        while (temp != nullptr) {
            if (cnt % 2) {
                head1->next = temp;
                head1 = head1->next;
            } else {
                head2->next = temp;
                head2 = head2->next;
            }
            temp = temp->next;
            cnt++;
        }
        // 断开两个链表的尾节点
        head1->next = nullptr;
        head2->next = nullptr;

        // 创建合并链表的虚拟头节点
        ListNode dummy3;
        ListNode* head3 = &dummy3;
        head1 = dummy1.next;
        head2 = dummy2.next;

        // 合并两个链表
        while (head1 != nullptr && head2 != nullptr) {
            head3->next = head2;
            head3 = head3->next;
            head2 = head2->next;

            head3->next = head1;
            head3 = head3->next;
            head1 = head1->next;
        }

        // 处理剩余节点
        if (head1 != nullptr) {
            head3->next = head1;
        }
        if (head2 != nullptr) {
            head3->next = head2;
        }

        return dummy3.next;
    }
};

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla