LeetCode | 24.两两交换链表中的节点
这次来写一下 LeetCode 的第 24 题，两两交换链表中的节点。
题目描述
题目直接从 LeetCode 上截图过来，题目如下：
image
上面的题就是 两两交换链表中的节点 题目的截图，同时 LeetCode 给出了一个函数的定义，然后要求实现链表两两交换的函数体。函数定义如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head){
}
从定义上看，是一个单链表，单链表只能顺着节点的指针依次找下去，而不能往回找。
问题分析
这个题目看似简单，其实还是有几个坑在里面的。听我慢慢道来。
先来看看，链表最初的情况，如下图：
image
最初链表的头指向第一个节点，我们首先要交换的是第一个节点和第二个节点，根据指针来看，只要让第一个节点的 next 指向第三个节点，然后让第二个节点的 next 指向第一个节点就可以了。在交换之前，首先要有一个指针（pre）指向第一个节点、还要有一个指针（cur）指向第二个节点，当然再准备一个指针（new）指向第三个节点。有了这些指针，就可以完成我们的交换了，如下图：
image
当交换完成以后，就接着移动这三个指针，进行下一次的交换。这样就构成了一个循环，怎么来判断是否循环？让 new = head，当 new 为 NULL 或者 new->next 为 NULL 的时候，就说明没有节点或者只剩一个节点了，就不用再交换了，这样循环就结束了。
以上看似完成了，其实还是有一个问题，我们接着推第二步交换试试。如下图：
image
开始第二轮交换的时候，指针的位置是这样的，然后按照前面的指针交换的方式进行交换。图下图：
image
交换完后的链表成了这个样子，但是仔细观察，不知道是否观察出了问题。我们的 4 号节点没有办法遍历到了。因为 1 号节点的指针仍然指向着 3 号节点，而经过交换，要把 4 号节点放到 3 号节点的前面。那么，也就是说，除了要完成 3 号节点和 4 号节点的交换，还要修正 1 号节点中 next 的指向。而此时，我们已经没有指针指向 1 号节点了。所以，我们增加一个指针 tmp 来指向 pre 指针就可以了，以后通过 tmp 指针的 next 来修正即可。修正后如下图：
image
当以后两个节点交换完成后，将 pre 指针赋值给 tmp 指针即可。
这样看似完成了，那么还有问题么？问题还是有的，我们的 head 指针一直指向的是 1 号节点，但是实际的链表头节点已经是 2 号节点了。当函数执行完成时，需要返回新的链表头节点，要怎么返回呢？我这里又增加了一个新的指针 result 来记录新的头节点，当循环完成以后，直接返回 result 就可以了。
上面的步骤就算完成了，几个问题其实都是我在写代码的时候遇到的。虽然步骤是完成了，但是我觉得我的代码应该还是有简化的空间的。暂时没有再去考虑了。
代码实现
上面说了那么多，其实代码反倒不是很复杂。代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head){
struct ListNode *new = head;
struct ListNode *pre = NULL;
struct ListNode *cur = NULL;
// 如果链表本身就是空的，那么就直接返回好了
if (head == NULL) {
return head;
}
// 不管链表有多少节点，只要大于等于两个节点，那么新的链表头都是第二个节点
struct ListNode *result = head;
if (head->next != NULL) {
result = head->next;
}
struct ListNode *tmp = NULL;
while (new != NULL && new->next != NULL) {
// 设置 pre 和 cur 的位置
pre = new;
cur = new->next;
new = new->next->next;
// 交换
pre->next = cur->next;
cur->next = pre;
// 这就是在第二次以及以后交换中要修正的部分
if (tmp != NULL) tmp->next = cur;
// 为了修正，需要保留当前交换的前一个节点
tmp = pre;
}
return result;
}
注释是我刚刚加上去的，其实自己整理了一遍，发现思路比当时写的时候清晰了许多。整理和总结真的是挺重要的。
提交结果
在写完 swapPairs 函数体后，点击右下角的 “执行代码”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “提交” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，如果没有通过，会给出失败的那一组测试用例，我们继续修改代码。我们以上代码 “提交” 以后的截图如下：
image
我觉得在内存消耗上应该可以更小一些，我为了截这个图，重新提交了代码，在提交代码前还修改了几行代码，内存消耗也由 5.5 MB 变为了 5.4 MB，通过梳理自己还是能找到改进空间，给自己点个赞。
