分析

• 本题的考点：链表。

• 我们发现头结点可能会变，因此需要使用虚拟头结点，这样比较方便。

• 这里需要使用到三个指针，其中指针a、b指向需要交换的两个节点，指针p指向a的前一个节点，做如下图的变换：

代码

• C++

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {

        auto dummy = new ListNode(-1);
        dummy->next = head;
        for (auto p = dummy; p->next && p->next->next; ) {
            auto a = p->next, b = a->next;
            p->next = b;
            a->next = b->next;
            b->next = a;
            p = a;
        }
        return dummy->next;
    }
};

• Java

class Solution {
    public ListNode swapPairs(ListNode head) {

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        for (ListNode p = dummy; p.next != null && p.next.next != null; ) {
            ListNode a = p.next, b = a.next;
            p.next = b;
            a.next = b.next;
            b.next = a;
            p = a;
        }
        return dummy.next;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为链表长度。

• 空间复杂度：$O(1)$。