技术图文：双指针在链表问题中的应用
背景
最近这段时间团队在进行算法刻意练习活动，我带着同学们刷 leetcode 的“腾讯精选练习（50）题”，参见：我是如何组织“算法刻意练习活动”的？
在做题的过程中，同学们讨论比较多的是链表中遇到的问题，我在这里为大家总结一下，双指针在链表问题中的应用。
技术分析
第一个问题：删除链表中的第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
做这个题目的思路就是，利用两个指针，开始时都指向头结点，先让一个指针顺着链表移动 N 个节点，然后两个指针同时移动，当前面的指针移动到 null 时，后面的指针就指向需要删除的节点位置。
代码如下：
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) { val = x; }* }*/
public class Solution
{public ListNode RemoveNthFormEnd(ListNode head, int n){ListNode temp1 = head;ListNode temp2 = head;int len = 0;int index = 0;while (temp1 != null){temp1 = temp1.next;len++;if (index == n){break;}index++;}if (len == n){head = head.next;return head;}while (temp1 != null){temp1 = temp1.next;temp2 = temp2.next;}temp2.next = temp2.next.next;return head;}
}
第二个问题：对单链表中的元素进行排序
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
如果待排的元素存储在数组中，就是我们的并归排序了。而这些元素存储在链表中，我们无法直接利用并归排序，只能借鉴并归排序的思想对算法进行修改。
并归排序的思想是将待排序列进行分组，直到包含一个元素为止，然后回溯合并两个有序序列，最后得到排序序列。
对于链表我们可以使用双指针的方式对链表节点进行分组。第一个指针每次移动两个节点，另一个指针每次移动一个节点，当前面的指针移动到 null 时，后面的指针刚好移动到中间位置，这样我们就可以根据中间节点将链表分成两个部分，即完成了对节点的分组。
代码如下：
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) { val = x; }* }*/public class Solution
{public ListNode SortList(ListNode head){if (head == null)return null;return MergeSort(head);}private ListNode MergeSort(ListNode node){if (node.next == null){return node;}ListNode fast = node;ListNode slow = node;ListNode cut = null;while (fast != null && fast.next != null){cut = slow;slow = slow.next;fast = fast.next.next;}cut.next = null;ListNode l1 = MergeSort(node);ListNode l2 = MergeSort(slow);return MergeTwoLists(l1, l2);}private ListNode MergeTwoLists(ListNode l1, ListNode l2){ListNode pHead = new ListNode(int.MaxValue);ListNode temp = pHead;while (l1 != null && l2 != null){if (l1.val < l2.val){temp.next = l1;l1 = l1.next;}else{temp.next = l2;l2 = l2.next;}temp = temp.next;}if (l1 != null)temp.next = l1;if (l2 != null)temp.next = l2;return pHead.next;}
}
第三个问题：判断单链表是否为循环链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
通常情况下，判断是否包含了重复的元素，我们使用 Hash 的方式来做。对于单链表的这种场景，我们也可以使用双指针的方式。
第一个指针每次移动两个节点，第二个指针每次移动一个节点，如果该链表存在环的话，第一个指针一定会再次碰到第二个指针，反之，则不存在环。
比如：head = [1,2,3,4,5]
第一个指针：1 3 5 2 4 1
第二个指针：1 2 3 4 5 1
代码如下：
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public bool HasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if (fast == slow)return true;}return false;}
}
总结
以上对双指针在链表中的应用做了一个总结，希望能够对大家有所帮助。今天就到这里吧！See You！
相关图文：
- 资料分享：数学建模资料分享 – 图论部分
- 资料分享：数学建模资料分享 – 神经网络部分
- 如何利用 C# 实现 K 最邻近算法？
- 如何利用 C# 实现 K-D Tree 结构？
- 如何利用 C# + KDTree 实现 K 最邻近算法？
- 如何利用 C# 对神经网络模型进行抽象？
- 如何利用 C# 实现神经网络的感知器模型？
- 如何利用 C# 实现 Delta 学习规则？
- 如何利用 C# 实现 误差反向传播 学习规则？
- 如何利用 C# 爬取带 Token 验证的网站数据？
- 如何利用 C# 向 Access 数据库插入大量数据？
- 如何利用 C# + Python 破解猫眼电影的反爬虫机制？
相关文章：
[BuildRelease]build number / id
build number， 也称为build id， 在build release的流程中唯一标示一个build，也是正式的产品的product version 和file version后两位（Major.minor.xxx.xxx）的来源，可以使用合适的方法将build number转化到p…
Windows Azure Storage (25) Azure Append Blob
《Windows Azure Platform 系列文章目录》 在笔者之前的文章中，我们介绍了Azure Blob 有两种：Block Blob和Page Blob。 在这里笔者介绍Blob的第三种：Append Blob。 概念： 1.Append Blob概念类似于Block Blob，因为都是由…
学python培训到底能干嘛
Python是在人工智能领域发挥着很重要的作用的，现在依旧有很多人对Python这项技术不是很了解，学Python培训到底能干嘛?下面小编来为大家做下详细的介绍。 python其实并不难学，对于初学者和完成普通任务，Python语言是非常简单易用的…
使用VB.NET加快代码开发速度
以前在学校时，编写代码都是使用C#，习惯了C#的代码习惯，等工作后由于工作需要逐渐的开始采用了VB.NET开发项目，渐渐地喜欢上了VB.NET，现在我就罗列一些VB.NET加速代码开发的方法。 一、智能感知 做.NET开发的许多人都知…
技术图文：举例详解Python中 split() 函数的使用方法
背景 这篇文章主要介绍Python中的split()函数的使用方法，split()函数通常用于将字符串切片并转换为列表，需要的朋友可以参考一下。 技术分析 Python中有split()和os.path.split()两个函数，具体作用如下： split()：拆…
Burning
转载于:https://www.cnblogs.com/kuiyuan/archive/2011/09/02/2163621.html
UI设计工作好找吗?有哪些面试技巧?
最近有很多学习UI设计的学员，想要了解UI设计学成之后是否好找工作?对于后期的面试有哪些技巧?下面小编整理的这些希望可以帮助到大家，来看看下面的详细介绍。 UI设计工作好找吗?有哪些面试技巧? 作品：很多初级小白的问题所在就是缺少大量…
刻意练习：Python基础 -- Task10. 类与对象
背景 我们准备利用17天时间，将 “Python基础的刻意练习” 分为如下任务： Task01：变量、运算符与数据类型（1day）Task02：条件与循环（1day）Task03：列表与元组（…
CentOS 7更新时出现Multilib version problems
这两天在更新CentOS7系统时，出现了Multilib version problems错误，执行命令： # yum update 出现了的错误信息： .... ---> Package libcap-ng.i686 0:0.7.5-4.el7 will be installed ---> Package libstdc.i686 0:4.8.5-16.e…
HTTP 错误 404.13 - Not Found 请求筛选模块被配置为拒绝超过请求内容长度的请求。...
把以下内容加在web.config的<system.webServer>节点 <security><requestFiltering ><requestLimits maxAllowedContentLength"1024000000" ></requestLimits></requestFiltering></security> 上述中maxAllowedContentLeng…
APP自动化测试过程概述
对于Android App的自动化测试框架的使用，其实在很多书上面都会有说明，我们可以先来看一个常用的自动化测试实例，先不说框架，主要是测试用户操作的模拟、执行结果的判断，以便获得对测试自动化的理解与认识。 案例需求如…
MFC最小化到系统托盘
在VC中，想实现将MFC最小化到系统托盘，需要调用NOTIFYICONDATA类，并注册相应的消息，以下详细讲解如何实现： 第一步，声明一个NOTIFYICONDATA类，也就是NOTIFYICONDATA NotifyIcon;该句可以放在Dlg类…
资料分享：推荐一本《简单粗暴TensorFlow 2.0》开源电子书！
背景 本开源电子书是一篇精简的 TensorFlow 2.0 入门指导，基于 TensorFlow 的 Eager Execution（动态图）模式，力图让具备一定机器学习及 Python 基础的开发者们快速上手 TensorFlow 2.0。 本开源电子书的所有代码基于 TensorFlow…
JS设计模式-观察者模式
观察者（又称发布订阅）模式定义了对象间的一种一对多的依赖关系，以便一个对象的状态发生变化时，所有依赖于它的对象都得到通知并自动刷新。原文链接 应用场景 当用户在网页执行一些操作（如点击）后就需要执行…
如何理解JS的单线程?
JS本质是单线程的。也就是说，它并不能像JAVA语言那样，两个线程并发执行。 但我们平时看到的JS，分明是可以同时运作很多任务的，这又是怎么回事呢? 首先，JS的代码，大致分为两类，同步代码和异步代…
Fedora 14下安装使用rarlinux
安装Fedora 14后，其默认情况下不能解压RAR文档，因为系统自带的解压软件不支持RAR格式文档，但由于经常要用到RAR文档，因此就必须安装一个RAR软件。Linux版的RAR下载链接： http://www.rarlab.com/download.htm 以rarlinu…
技术图文：如何利用 Python 做一个简单的定时器类？
背景 今天在B站上看有关 Python 最火的一个教学视频，零基础入门学习 Python，这也是我们 Python基础刻意练习活动 的推荐视频教程。 在学习魔法方法的时候，有一节视频是制作一个简单的定时器，基本要求如下： 定制一个计…
20、C#里面方法的创建和显示
在C#里面，和Java也是一样的，都是可以创建方法的。这里所说的方法，就是其它编程语言里面的函数、子程序、过程等。创建的方法有两种：一种是没有返回值的方法。一种是有返回值的方法。无论是哪种方法，其实都是很简单的。…
优秀的Java程序员应具备哪些编程技术?
想要成为一名合格的java程序猿，需要学习的知识是有很多的，但是基础知识一定要非常牢固，基础不牢固的程序员，随时都会被新的知识和技术所淘汰，下盘不稳风一吹就倒，那么具体作为一个优秀的Java程序员应具备哪…
asp.net 后台事件掉用前台js
在下面的例子中，我们在一个 .aspx 文件中声明了一个 TextBox 控件和一个 Label 控件。当您更改了 TextBox 中的值，并且在 TextBox 外单击时，change 子例程就会被执行。change 子例程会向 Label 控件写一条文本： <script runat&…
Android -- 利用Broadcast开启Service
Broadcast和Service都是Android四大组建之一的。 这里的广播是动态的，自己注册的一个广播。 这种最典型的用法就是利用开机广播，然后再起自己的服务，也就是在Android手机中做到开启启动。 Service与Broadcast …
资料分享：推荐一本《李宏毅机器学习》开源电子书！
背景 今天在 github 上看到了 datawhale 发布的 李宏毅机器学习笔记。 https://datawhalechina.github.io/leeml-notes 其目录如下： P1 机器学习介绍P2 为什么要学习机器学习P3 回归P4 回归-演示P5 误差从哪来？P6 梯度下降P7 梯度下降（用…
Python 中常见的配置文件写法
相信学习Python或者正在进行Python工作的小伙伴都会有一个疑问，为什么要写配置文件呢?在开发过程中，我们常常会用到一些固定参数或者是常量。对于这些较为固定且常用到的部分，往往会将其写到一个固定文件中，避免在不同的模块代码…
技术图文：Python描述符 (descriptor) 详解
背景 今天在B站上学习“零基础入门学习Python”这门课程的第46讲“魔法方法：描述符”，这也是我们组织的 Python基础刻意练习活动 的学习任务，其中有这样的一个题目。 练习要求： 先定义一个温度类，然后定义两个描述符…
[转]自定义hadoop map/reduce输入文件切割InputFormat
本文转载自：http://hi.baidu.com/lzpsky/blog/item/99d58738b08a68e7b311c70d.html hadoop会对原始输入文件进行文件切割，然后把每个split传入mapper程序中进行处理，FileInputFormat是所有以文件作 为数据源的InputFormat实现的基类&…
使用深度学习检测DGA（域名生成算法）——LSTM的输入数据本质上还是词袋模型...
from:http://www.freebuf.com/articles/network/139697.html DGA（域名生成算法）是一种利用随机字符来生成C&C域名，从而逃避域名黑名单检测的技术手段。例如，一个由Cryptolocker创建的DGA生成域xeogrhxquuubt.com，如…
学习Python开发培训有用吗
学习Python开发培训有用吗?这是目前很多人都比较关注的一个问题，Python语言在最近几年是广受IT互联网行业关注的， 下面我们就针对这问题来详细的分析一下。 学习Python开发培训有用吗?Python是被广泛使用的高级编程语言，Python解释器本身几…
Web性能优化实践——应用层性能优化
随着公司项目的进一步推广，用户数量的增加，已经面临着单台服务器不能负载的问题。 这次的优化由于时间关系主要分两步走，首先优化应用层代码以提高单台服务器的负载和吞吐率。之后再进行分表，引入队列、MemCached等分布式应用。 项…
技术图文：Python魔法方法之属性访问详解
背景 今天在B站学习“零基础入门学习 Python”中的第45节“魔法方法：属性访问”，这也是我们组织的 Python基础刻意练习活动 的学习任务，其中有这样的一个题目。 练习要求： 写一个矩形类，默认有宽和高两个属性。如果…
chmod权限设置
drwxr-xr-x. 7 root root 4096 Sep 26 20:16 sysconfig-rw-r--r--. 1 root root 1150 Aug 31 18:46 sysctl.conflrwxrwxrwx. 1 root root 14 Aug 31 17:21 system-release -> centos-release例如：-rw-r--r--第一个代表文件类型:-普通文件：…