Java栈、队列、链表常见算法浅析

数据是基础，算法是灵魂

本文出自门心叼龙的博客，属于原创类容，转载请注明出处。https://blog.csdn.net/geduo_83/article/details/86549973

这篇文章我们只谈算法的具体实现思考过程，并没有相关代码实现，代码的实现过程请参见我的另外一篇文章：Java数据结构与算法中级篇之栈、队列、链表

源码下载地址：https://download.csdn.net/download/geduo_83/10913510

初级篇：Java数据结构与算法初级篇之数组、集合和散列表
中级篇：Java数据结构与算法中级篇之栈、队列、链表
高级篇：Java数据结构与算法高级篇之树、图

理论篇：Java数组、集合、散列表常见算法浅析
理论篇：Java栈、队列、链表常见算法浅析
理论篇：Java树、图常见算法浅析

前言：

在2018年9月份，也就是前几个月，阿里巴巴搞了一个全球数学竞赛，一石激起千层浪，各路豪杰纷纷参战，移动互联网的狂潮已经结束了，下一个风口将是人工智能，搞人工智能就离不开数学算法，马云醉翁之意不在酒，而在抢夺全球的顶尖级数学人才，可见算法的重要性。

我们日常开发都在关注界面和用户体验，在算法上往往要求不高，一直有打算写几篇关于算法的文章，我在网上搜索了下，基本都是直接贴算法代码，并没有分析这一步步为什么要这么实现，也许我没有发现，分析很重要，有了思路再去实现也是顺理成章的事情了，所以今天就写下了下面的这些文字。

1.自定义实现一个栈

我们知道数组是一切数据结构的基础，其他的大部分数据结构都是在数组的基础上实现的，例如上一篇我们讲过的集合，散列表，以及这一篇我们即将讲到的栈和队列。

栈的主要特点就是只能在一端进行数据添加和删除操作的数据结构，它和集合一样离不开两个最基本的操作添加和删除，也就是数据的入栈和出栈，通过一个指针来记录当前下标，入栈就是给下标为size++的这个元素赋值，注意一点当size和源数组的长度相等的时候就给源数组进行扩容。出栈就是取出size--这个元素的值，取出之后要给size--这个位置的元素赋值为0。

2.自定义一个队列

栈是入栈、出栈的操作，队列的是入列、出列的操作，我们要实现的是一个循环队列，声明两个指针，一个头指针，一个尾指针，头指针用于数据的入列操作，尾指针用于数据的出列操作。

我们先来分析入列，入列数据能一直加下去吗？不可能的，他是一个循环队列肯定有加满的时候，什么时候满了？当对头指针加1和数组长度取余如果到了尾指针的位置，那么就说明队列满了就直接返回了，否则就给头指针的元素赋值，赋值完毕一定要注意头指针要往前挪动一个位置。因为是循环队列所以移动指针就不是i++那么简单了，而是源指针＋1和数组长度取余。

分析完了数据入列，数据出列就简单的多了，直接返回尾指针所指向的数组元素即可，出列注意一点何时队列空了？其实很简单只要头指针和尾指针相等了就说明队列已经没有数据了。尾指针移动的逻辑和头指针一样这里就不在赘述了。

3.自定义实现一个链表

链表的实现首先需要声明一个节点对象，节点对象有两个成员变量，一个是节点的值data，一个是下一个节点Note。

另外就是我们的核心对象链表对象，想一想他都有哪些成员变量？要遍历离不开头节点，要添加一个新元素离不开尾节点，另外我们有时候需要获取一下链表的长度，分析到这里很显然构成链表对象有三个基本的成员变量，头节点，尾节点，长度size。为了简单起见我我们就实现它的一个核心方法添加方法，当在添加一个新节点的时候，首先需要建立一个Note，接着要建立链接关系，如果头节点为空？说明是头一次添加则给头节点赋值，否则把当前节点赋值给尾节点的下家元素，最后一步把当前节点赋值给尾结点就ok了。核心逻辑就是头次给头节点赋值，以后都是当前节点赋值给尾结点的下家节点，并把当前节点赋值给尾结点。不要忘了每次添加一个新的元素都需要给size加1，这样一个简单的链表就实现了，另外需要提供一个返回头结点的方法以便我们对链表进行遍历等操作。

4.判断链表有没有环

法1，计数法，原理和我们上一篇文章讲过的判断一个数组里面有没有重复元素的道理是一样的，遍历链表中的每一个元素，如果没有就往Set集合里面塞，有就直接返回了。

法2，差速法，声明两个指针，一个快指针，一个慢指针。遍历链表，快指针一次走两步，慢指针一次走一步，有环则必回相遇。链表遍历的结束条件需要注意一下，快节点不为空且快节点的下家节点也不为空。

5.查找有环链表的入口节点

其实查找链表入口节点的算法是在判断一个链表有没有环的算法差速法的基础上实现的，如果发现有环则退出循环，接着慢节点回到头节点，然后快节点和慢节点一直往前移动下去，要注意此时快节点和慢节点都是一次挪动一个位置，若相遇则退出循环，此时的慢节点就是我们所要查找的入口节点。

为什么这样操作就能找到入口节点？因为这里面存在一个非常重要的原理，就是从头节点到入口节点的距离等于从相遇节点到入口节点的距离，为什么是这样的，我们来推导一下，我们知道慢指针一次走一步，快指针一次走两步，初始快指针和慢指针都在头节点s0，f0，我们开始移动指针s1,f2 ; s2,f4 ; s3,f6…因此我们得出一个结论，快指针所走的距离始终是慢指针距离的2倍，那么如果设头节点到入口节点的距离为m，从入口节点到相遇节点的距离为x，从相遇节点到入口节点的距离为y，那么当快慢节点相遇时则有2倍的慢节点走的距离等于快节点所走的距离，即就是:2(m+x) = m + x + y + x ; 也就是: 2m + 2x = m + 2x + y ;即可得: m = y;所以当慢节点再次回退到头节点和快节点同时开始移动时，注意了此时快节点一次移动一个节点，那么再次相遇的节点就是循环链表的入口节点。

6.反转一个链表

这个问题有两种解法，法1指针法，这种方法的主要思想就是通过一个遍历，每走一步把当前节点挪动到新链表的头部即可，法2是数组法，我们主要讲第二种算法，要反转那么就要倒叙遍历，怎么办？对于链表来说很困难，如果是一个数组就方便多了，如果我们将链表的元素存入数组将何如？豁然开朗，对就先将链表元素存入数组，然后在倒叙遍历这个数组，遍历的时候将节点元素依次插入新链表即可。注意了把最后一个节点的next链赋值为null否则会出现循环链表。

7.删除链表的倒数第n个节点

要删除倒数第n个节点，那么我们只要找到要删除的那个节点前面的那个节点pb,然后再执行pb.next = pb.next.next，这样就轻松的把第n个节点删除了，我们想了，要删除倒数那个节点，我们先找到正数的那个节点指针pa，然后再声明一个指向链表的头部指针pb，以然后两个指针同时移动，直到pa移动到最后，则此时节点pb就是我们要删除那个节点的前面那个节点，我们再执行pb.next = pb.next.next ，同时返回头节点就ok了。

8.合并两个有序链表

简单粗暴一点，直接将两个链表转化为两个数组，然后再将两个数组合并为一个数组，然后对新数组排序，最后再将该数组转化为一个链表即可解决问题。

第二种方法通过指针法，首先声明两个指针，一个头指针，一个尾指针，接着开始遍历两个链表，每走一步比较一下当前的两个元素的大小，如果哪个小就把他添加到尾指针，直到循环完毕，最后一步把不为空的那个链表节点添加到尾指针的屁股后面即可。

小结：

好了，今天我们关于栈、队列、链表常见算法的分析就讲到这里，另外附上源码下载地址，和另外几篇关于算法和数据结构的文章，有任何问题，请在文章下方给我留言。

源码下载地址：https://download.csdn.net/download/geduo_83/10913510

初级篇：Java数据结构与算法初级篇之数组、集合和散列表
中级篇：Java数据结构与算法中级篇之栈、队列、链表
高级篇：Java数据结构与算法高级篇之树、图

理论篇：Java数组、集合、散列表常见算法浅析
理论篇：Java栈、队列、链表常见算法浅析
理论篇：Java树、图常见算法浅析