题目描述

给定一个单向链表，依次交换每一对相邻的两个结点，返回修好后的链表头结点。

链表结点的数据结构：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

样例

输入：1->2->3->4
输出：2->1->4->3

额外要求

• 不得修改链表中结点的 val 值，仅可以使用常数的空间。

算法

(模拟) $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(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy -> next = 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;
    }
};