LeetCode (24):两两交换链表中的节点

栏目: IT技术 · 发布时间: 4年前

内容简介:LeetCode 相关的文章:这次来写一下 LeetCode 的第 24 题,两两交换链表中的节点。

LeetCode 相关的文章:

1、 LeetCode | 206.反转链表

这次来写一下 LeetCode 的第 24 题,两两交换链表中的节点。

题目描述

题目直接从 LeetCode 上截图过来,题目如下:

LeetCode (24):两两交换链表中的节点

上面的题就是 两两交换链表中的节点  题目的截图,同时 LeetCode 给出了一个函数的定义,然后要求实现链表两两交换的函数体。函数定义如下:

/**

* Definition for singly-linked list.

* struct ListNode {

*     int val;

*     struct ListNode *next;

* };

*/

struct ListNode* swapPairs( struct ListNode* head){

}

从定义上看,是一个单链表,单链表只能 顺着节点的指针依次找下去,而不能往回找。

问题分析

这个题目看似简单,其实还是有几个坑在里面的。听我慢慢道来。

先来看看,链表最初的情况,如下图:

LeetCode (24):两两交换链表中的节点

最初链表的头指向第一个节点,我们首先要交换的是第一个节点和第二个节点,根据指针来看,只要让第一个节点的 next 指向第三个节点,然后让第二个节点的 next 指向第一个节点就可以了。在交换之前,首先要有一个指针(pre)指向第一个节点、还要有一个指针(cur)指向第二个节点,当然再准备一个指针(new)指向第三个节点。有了这些指针,就可以完成我们的交换了,如下图:

LeetCode (24):两两交换链表中的节点

当交换完成以后,就接着移动这三个指针,进行下一次的交换。这样就构成了一个循环,怎么来判断是否循环? 让 new = head,当 new 为 NULL 或者 new->next 为 NULL 的时候,就说明没有节点或者只剩一个节点了,就不用再交换了,这样循环就结束了。

以上看似完成了,其实还是有一个问题,我们接着推第二步交换试试。如下图:

LeetCode (24):两两交换链表中的节点

开始第二轮交换的时候,指针的位置是这样的,然后按照前面的指针交换的方式进行交换。图下图:

LeetCode (24):两两交换链表中的节点

交换完后的链表成了这个样子,但是仔细观察,不知道是否观察出了问题。 我们的 4 号节点没有办法遍历到了。因为 1 号节点的指针仍然指向着 3 号节点,而经过交换,要把 4 号节点放到 3 号节点的前面。 那么,也就是说, 除了要完成 3 号节点和 4 号节点的交换,还要修正 1 号节点中 next 的指向。 而此时,我们已经没有指针指向 1 号节点了。所以,我们增加一个指针 tmp 来指向 pre 指针就可以了,以后通过 tmp 指针的 next 来修正即可。修正后如下图:

LeetCode (24):两两交换链表中的节点

当以后两个节点交换完成后,将 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 函数体后,点击右下角的 “ 执行代码 ”,然后观察  “输出” 和 “预期结果”  是否一致,一致的话就点击 “ 提交 ” 按钮。点击 “提交” 按钮后,系统会使用更多的测试用例来测试我们写的函数体, 如果所有的测试用例都通过了,那么就会给出 “通过” 的字样, 如果没有通过,会给出失败的那一组测试用例,我们继续修改代码 。我们以上代码 “提交” 以后的截图如下:

LeetCode (24):两两交换链表中的节点

我觉得在内存消耗上应该可以更小一些,我为了截这个图,重新提交了代码,在提交代码前还修改了几行代码,内存消耗也由 5.5 MB 变为了 5.4 MB,通过梳理自己还是能找到改进空间,给自己点个赞。

LeetCode (24):两两交换链表中的节点

喜欢就点在看哦~


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Network Algorithmics,

Network Algorithmics,

George Varghese / Morgan Kaufmann / 2004-12-29 / USD 75.95

In designing a network device, you make dozens of decisions that affect the speed with which it will perform - sometimes for better, but sometimes for worse. "Network Algorithmics" provides a complete......一起来看看 《Network Algorithmics,》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

URL 编码/解码
URL 编码/解码

URL 编码/解码

MD5 加密
MD5 加密

MD5 加密工具