LeetCode (206):反转链表

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

内容简介:LeetCode 是著名的练习数据结构与算法的网站,很多学习程序设计的人都在刷上面的题来巩固和提高自己的数据结构以及算法的能力。同时,该网站的很多数据结构及算法题都是面试中的真题。我刷过的题目不算多,我准备把我做过的题目再逐步的整理一下。虽然之前也有整理过,但是基本上是把题目和答案粘贴上就算完事了。这样做其实并没有把解题的过程留下,那么也就既起不到总结的作用,也算不上是分享了。因此,我还是打算认真的整理一下。我的整理不会按照题目的顺序去整理,我只能是按照我已经完成的题目去整理。今天整理的是

LeetCode 是著名的练习数据结构与算法的网站,很多学习程序设计的人都在刷上面的题来巩固和提高自己的数据结构以及算法的能力。同时,该网站的很多数据结构及算法题都是面试中的真题。

我刷过的题目不算多,我准备把我做过的题目再逐步的整理一下。虽然之前也有整理过,但是基本上是把题目和答案粘贴上就算完事了。这样做其实并没有把解题的过程留下,那么也就既起不到总结的作用,也算不上是分享了。因此,我还是打算认真的整理一下。

我的整理不会按照题目的顺序去整理,我只能是按照我已经完成的题目去整理。今天整理的是 第 206 题 “反转链表”

题目描述

题目直接从 LeetCode 拿来,题目如下:

LeetCode (206):反转链表

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

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* reverseList(struct ListNode* head){


}

从函数定义可以看出,它是一个单链表,单链表的特点是当前 结点 通过其指针域可以找到下一个结点,而无法通过当前结点找到它的上一个结点。

问题分析

反转单链表的思路还是比较简单的,关键是代码的实现,我们来简单的分析一下代码要完成的功能。

把问题的规模缩小到 3 个结点,情况如下:

1 -> 2 -> 3 -> NULL

反转链表,后的情况如下:

3 -> 2 -> 1 -> NULL

reverseList 的参数 head 指向了链表的 1 结点,只要我们循环遍历整个链表,并且让当前结点的指针指向前一个结点即可。但是单链表只能沿着一个方向进行遍历,无法找到上一个结点。因此,在进行遍历的时候,必须要有两个指针,一个指针用来指向当前元素、另一个指针用来指向当前元素的上一个元素,两个指针同时移动,这样让当前元素的指针就可以指向上一个元素了。

但是,这样就会有另外一个问题,当前元素的指针是指向下一个元素的,如果将当前元素的指针指向了上一个元素,那么当前元素和下一个元素就断链了,也就是无法找到当前元素的下一个元素了。那么,只要在当前元素的指针指向上一个元素之前,就先让另外一个指针指向当前元素的下一个元素,那么就可以了。

比如,当前元素是 2 结点,指向 2 结点的指针为 cur。指向上一个结点的指针为 per,也就是说 per 指针指向 1 结点。2 结点的下一个结点是 3 结点,在 2 结点的指针指向 1 结点之前,让 tmp 指向下一个结点。

当然了,思路是这样的,三个指针的关系也是这样的,但是实现代码的时候只要能维持 3 个指针之间的关系就可以了。

代码实现

代码还是比较简单的,代码如下:

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/



struct ListNode* reverseList(struct ListNode* head){

/* 指向第一个结点 */

struct ListNode *cur = head;

struct ListNode *per = NULL;

struct ListNode *tmp = NULL;


/* 判断当前结点是否为NULL */

while (cur) {

/* 将当前结点保存到tmp中 */

tmp = cur;

/* 当前结点移动到下一个结点 */

cur = cur->next;

/* 当前结点的指针指向上一个结点 */

tmp->next = per;

/* 上一个结点指向当前结点 */

per = tmp;

}


return per;

}

提交结果

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

LeetCode (206):反转链表

我的代码是否最优,我并不清楚,我也没有去阅读别人的代码和解题思路。如果有不懂的,欢迎给我留言,我们一起讨论。

LeetCode (206):反转链表

喜欢就点在看哦~


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

查看所有标签

猜你喜欢:

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

白话大数据与机器学习

白话大数据与机器学习

高扬、卫峥、尹会生 / 机械工业出版社 / 2016-6 / 69

本书通俗易懂,有高中数学基础即可看懂,同时结合大量案例与漫画,将高度抽象的数学、算法与应用,与现实生活中的案例和事件一一做了关联,将源自生活的抽象还原出来,帮助读者理解后,又带领大家将这些抽象的规律与算法应用于实践,贴合读者需求。同时,本书不是割裂讲解大数据与机器学习的算法和应用,还讲解了其生态环境与关联内容,让读者更全面地知晓渊源与未来,是系统学习大数据与机器学习的不二之选: ·大数据产业......一起来看看 《白话大数据与机器学习》 这本书的介绍吧!

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具