内容简介:LeetCode 相关的文章:这次来写一下 LeetCode 的第 24 题,两两交换链表中的节点。
LeetCode 相关的文章:
这次来写一下 LeetCode 的第 24 题,两两交换链表中的节点。
题目描述
题目直接从 LeetCode 上截图过来,题目如下:
上面的题就是 两两交换链表中的节点 题目的截图,同时 LeetCode 给出了一个函数的定义,然后要求实现链表两两交换的函数体。函数定义如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs( struct ListNode* head){
}
从定义上看,是一个单链表,单链表只能
顺着节点的指针依次找下去,而不能往回找。
问题分析
这个题目看似简单,其实还是有几个坑在里面的。听我慢慢道来。
先来看看,链表最初的情况,如下图:
最初链表的头指向第一个节点,我们首先要交换的是第一个节点和第二个节点,根据指针来看,只要让第一个节点的 next 指向第三个节点,然后让第二个节点的 next 指向第一个节点就可以了。在交换之前,首先要有一个指针(pre)指向第一个节点、还要有一个指针(cur)指向第二个节点,当然再准备一个指针(new)指向第三个节点。有了这些指针,就可以完成我们的交换了,如下图:
当交换完成以后,就接着移动这三个指针,进行下一次的交换。这样就构成了一个循环,怎么来判断是否循环? 让 new = head,当 new 为 NULL 或者 new->next 为 NULL 的时候,就说明没有节点或者只剩一个节点了,就不用再交换了,这样循环就结束了。
以上看似完成了,其实还是有一个问题,我们接着推第二步交换试试。如下图:
开始第二轮交换的时候,指针的位置是这样的,然后按照前面的指针交换的方式进行交换。图下图:
交换完后的链表成了这个样子,但是仔细观察,不知道是否观察出了问题。 我们的 4 号节点没有办法遍历到了。因为 1 号节点的指针仍然指向着 3 号节点,而经过交换,要把 4 号节点放到 3 号节点的前面。 那么,也就是说, 除了要完成 3 号节点和 4 号节点的交换,还要修正 1 号节点中 next 的指向。 而此时,我们已经没有指针指向 1 号节点了。所以,我们增加一个指针 tmp 来指向 pre 指针就可以了,以后通过 tmp 指针的 next 来修正即可。修正后如下图:
当以后两个节点交换完成后,将 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 函数体后,点击右下角的 “ 执行代码 ”,然后观察 “输出” 和 “预期结果” 是否一致,一致的话就点击 “ 提交 ” 按钮。点击 “提交” 按钮后,系统会使用更多的测试用例来测试我们写的函数体, 如果所有的测试用例都通过了,那么就会给出 “通过” 的字样, 如果没有通过,会给出失败的那一组测试用例,我们继续修改代码 。我们以上代码 “提交” 以后的截图如下:
我觉得在内存消耗上应该可以更小一些,我为了截这个图,重新提交了代码,在提交代码前还修改了几行代码,内存消耗也由 5.5 MB 变为了 5.4 MB,通过梳理自己还是能找到改进空间,给自己点个赞。
喜欢就点在看哦~
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- leetcode 24. 两两交换链表中的节点
- 画解算法:24. 两两交换链表中的节点
- 为您的 NIEM 交换建模
- RabbitMQ消息交换模式简介
- DSMM之数据交换安全
- 为何要用到三层交换机?监控系统中三层交换机选择的七项指标
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
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,》 这本书的介绍吧!