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，通过梳理自己还是能找到改进空间，给自己点个赞。