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):反转链表

喜欢就点在看哦~


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

查看所有标签

猜你喜欢:

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

HTTPS权威指南

HTTPS权威指南

[英] Ivan Risti? / 杨洋、李振宇、蒋锷、周辉、陈传文 / 人民邮电出版社 / 2016-9 / 99.00元

本书是集理论、协议细节、漏洞分析、部署建议于一体的详尽Web应用安全指南。书中具体内容包括:密码学基础,TLS协议,PKI体系及其安全性,HTTP和浏览器问题,协议漏洞;最新的攻击形式,如BEAST、CRIME、BREACH、Lucky 13等;详尽的部署建议;如何使用OpenSSL生成密钥和确认信息;如何使用Apache httpd、IIS、Nginx等进行安全配置。一起来看看 《HTTPS权威指南》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

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

HSV CMYK互换工具