美文网首页
LeetCode | 24.两两交换链表中的节点

LeetCode | 24.两两交换链表中的节点

作者: 码农UP2U | 来源:发表于2020-08-31 07:54 被阅读0次

    这次来写一下 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,通过梳理自己还是能找到改进空间,给自己点个赞。

    相关文章

      网友评论

          本文标题:LeetCode | 24.两两交换链表中的节点

          本文链接:https://www.haomeiwen.com/subject/lmoysktx.html