题目内容

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

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

示例

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

题解

本题是一道链表题，通过画图实现两个节点的交换过程，然后通过代码实现即可。这里注意如果链表结点数为偶数，则两两交换即可，如果链表结点数为奇数，则最后一个落单元素不用管。

大致过程如下：

由于本题是单链表，因此在实现的过程中，除了指向两个要交换的结点的指针外，还需要一个额外指针指向一对结点的前一个指针，保证交换后链表结构完整。

代码

/**
 * 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) {
        //这是一个节点交换的问题。可以通过画图，将过程明晰后直接写代码。
        //这里需要注意一个问题，就是如果节点个数为奇数，则最后一个未匹配的单节点可以不用交换。
        //还有就是，虚拟头结点在每次链表的两个节点交换位置后往后移动两位。
        auto dummy = new ListNode(-1);
        dummy -> next =  head;
        for(auto p = dummy; p -> next && p -> next -> next;){
            auto a = p -> next, b = p -> next -> next; //找到要交换的两个点
            p -> next = b;
            a -> next = b -> next;
            b -> next = a;
            p = a;
        }
        return dummy -> next;
    }
};