题目描述

给定一个链表，两两交换其中相邻的结点，并返回交换后的链表。

你不能只是单纯的改变结点内部的值，而是需要实际的进行结点交换。

样例

给定 1->2->3->4, 你应该返回链表 2->1->4->3。

算法

(模拟) $O(L)$

1. 添加虚拟头结点 dummy。
2. 定义 cur 指针初始指向 dummy。
3. 定义 first 为 cur->next，second 为 first->next；若 first 或 second 为空，则终止循环。
4. 按照一定的次序，修改 cur、first 和 second结点的 next 指针，具体参见代码。
5. 将 cur 指向修改后的 first，接着从第 3 步循环。

时间复杂度

• 仅遍历一遍所有结点，所以是 $O(L)$。

空间复杂度

• 仅使用常数的额外空间。

C++ 代码

/**
 * 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* dummy = new ListNode(0, head);
        ListNode* cur = dummy;

        while (cur != NULL) {
            ListNode* first = cur -> next;
            if (first == NULL)
                break;

            ListNode* second = first -> next;
            if (second == NULL)
                break;

            cur -> next = second;
            first -> next = second -> next;
            second -> next = first;

            cur = first;
        }
        return dummy -> next;
    }
};