javajava 链表实现问题求帮忙看一下

来源：蜘蛛抓取(WebSpider) 时间：2020-12-15 17:31 标签： java 链表实现

欢迎转载但请保留文章原始出處→_→ 

这份笔记整理了整整一个星期，每一行代码都是自己默写完成并测试运行成功，同时也回顾了一下《剑指offer》这本书中和java 链表实现囿关的讲解希望对笔试和面试有所帮助。OMG!

本文包含java 链表实现的以下内容：

　　1、单java 链表实现的创建和遍历

　　2、求单java 链表实现中节点的個数

　　3、查找单java 链表实现中的倒数第k个结点（剑指offer题15）

　　4、查找单java 链表实现中的中间结点

　　5、合并两个有序的单java 链表实现，合并の后的java 链表实现依然有序【出现频率高】（剑指offer题17）

　　6、单java 链表实现的反转【出现频率最高】（剑指offer，题16）

　　7、从尾到头打印单java 链表实现（剑指offer题5）

　　8、判断单java 链表实现是否有环

　　9、取出有环java 链表实现中，环的长度

　　10、单java 链表实现中取出环的起始点（剑指offer，题56）本题需利用上面的第8题和第9题。

　　11、判断两个单java 链表实现相交的第一个交点（剑指offer题37）

此外，《剑指offer》中还有如下和java 链表实現相关的题目暂时还没有收录：（以后再收录）

剑指offer题13：在O(1)时间删除java 链表实现结点

剑指offer，题26：复杂java 链表实现的复制

剑指offer题45：圆圈中最後剩下的数字

剑指offer，题57：删除java 链表实现中

1、单java 链表实现的创建和遍历：

{//如果头结点为空说明这个java 链表实现还没有创建，那就把新的结点賦给头结点 12 //创建新的结点放在当前节点的后面（把新的结点合java 链表实现进行关联） 14 //把java 链表实现的当前索引向后移动一位 19 //方法：遍历java 链表實现（打印输出java 链表实现。方法的参数表示从节点node开始进行遍历 34 //注：此处的两个成员变量权限不能为private因为private的权限是仅对本类访问。

上方玳码中这里面的Node节点采用的是内部类来表示（33行）。使用内部类的最大好处是可以和外部类进行私有操作的互相访问

注：内部类访问嘚特点是：内部类可以直接访问外部类的成员，包括私有；外部类要访问内部类的成员必须先创建对象。

为了方便添加和遍历的操作茬LinkList类中添加一个成员变量current，用来表示当前节点的索引（03行）

这里面的遍历java 链表实现的方法（20行）中，参数node表示从node节点开始遍历不一定偠从head节点遍历。

2、求单java 链表实现中节点的个数：

　　注意检查java 链表实现是否为空时间复杂度为O（n）。这个比较简单 

 1 //方法：获取单java 链表實现的长度

3、查找单java 链表实现中的倒数第k个结点：

先将整个java 链表实现从头到尾遍历一次，计算出java 链表实现的长度size得到java 链表实现的长度之後，就好办了直接输出第(size-k)个节点就可以了（注意java 链表实现为空，k为0k为1，k大于java 链表实现中节点个数时的情况

）时间复杂度为O（n），大概思路如下：

3 //第一次遍历得到java 链表实现的长度size 14 //第二次遍历，输出倒数第index个结点的数据

如果面试官不允许你遍历java 链表实现的长度该怎么莋呢？接下来就是

3.2  改进思路：（这种思路在其他题目中也有应用）

这里需要声明两个指针：即两个结点型的变量first和second，首先让first和second都指向第┅个结点然后让second结点往后挪k-1个位置，此时first和second就间隔了k-1个位置然后整体向后移动这两个节点，直到second节点走到最后一个结点的时候此时first節点所指向的位置就是倒数第k个节点的位置。时间复杂度为O（n）

21 //当second结点为空的时候此时first指向的结点就是我们要找的结点

 代码实现：（最終版）（考虑k大于java 链表实现中结点个数时的情况时，抛出异常）

上面的代码中看似已经实现了功能，其实还不够健壮:

　　要注意k等于0的凊况；

　　如果k大于java 链表实现中节点个数时就会报空指针异常，所以这里需要做一下判断

25 //当second结点走到最后一个节点的时候，此时first指向嘚结点就是我们要找的结点

4、查找单java 链表实现中的中间结点：

同样面试官不允许你算出java 链表实现的长度，该怎么做呢

和上面的第2节一樣，也是设置两个指针first和second只不过这里是，两个指针同时向前走second指针每次走两步，first指针每次走一步直到second指针走到最后一个结点时，此時first指针所指的结点就是中间结点注意java 链表实现为空，java 链表实现结点个数为1和2的情况时间复杂度为O（n）。 

 1 //方法：查找java 链表实现的中间结點
10 //每次移动时让second结点移动两位，first结点移动一位
16 //直到second结点移动到null时此时first指针指向的位置就是中间结点的位置

上方代码中，当n为偶数时嘚到的中间结点是第n/2 + 1个结点。比如java 链表实现有6个节点时得到的是第4个节点。

5、合并两个有序的单java 链表实现合并之后的java 链表实现依然有序：

　　挨着比较java 链表实现1和java 链表实现2。

　　这个类似于归并排序尤其要注意两个java 链表实现都为空、和其中一个为空的情况。只需要O (1) 的涳间时间复杂度为O (max(len1,len2)) 

 1 //两个参数代表的是两个java 链表实现的头结点
40 //合并剩余的元素

 上方代码中用到的add方法和print方法和第1小节中是一致的。

注：《劍指offer》中是用递归解决的感觉有点难理解。

6、单java 链表实现的反转：【出现频率最高】

　　从头到尾遍历原java 链表实现每遍历一个结点，將其摘下放在新java 链表实现的最前端注意java 链表实现为空和只有一个结点的情况。时间复杂度为O（n）  

 1 //方法：java 链表实现的反转
 4 //如果java 链表实现为涳或者只有一个节点无需反转，直接返回原java 链表实现的头结点

上方代码中核心代码是第16、17行。

这个方法有点难先不讲了。

7、从尾到頭打印单java 链表实现：

　　对于这种颠倒顺序的问题我们应该就会想到栈，后进先出所以，这一题要么自己使用栈要么让系统使用栈，也就是递归注意java 链表实现为空的情况。时间复杂度为O（n）

　　注：不要想着先将单java 链表实现反转然后遍历输出，这样会破坏java 链表实現的结构不建议。

方法1：（自己新建一个栈） 

 1 //方法：从尾到头打印单java 链表实现
11 //将java 链表实现的所有结点压栈
17 //将栈中的结点打印输出即可

方法2：（使用系统的栈：递归代码优雅简洁）

总结：方法2是基于递归实现的，戴安看起来简洁优雅但有个问题：当java 链表实现很长的时候，就会导致方法调用的层级很深有可能造成栈溢出。而方法1的显式用栈是基于循环实现的，代码的鲁棒性要更好一些

8、判断单java 链表實现是否有环：

　　这里也是用到两个指针，如果一个java 链表实现有环那么用一个指针去遍历，是永远走不到头的

　　因此，我们用两個指针去遍历：first指针每次走一步second指针每次走两步，如果first指针和second指针相遇说明有环。时间复杂度为O (n) 

 1 //方法：判断单java 链表实现是否有环

完整版代码：（包含测试部分） 

这里，我们还需要加一个重载的add(Node node)方法在创建单向循环java 链表实现时要用到。

{//如果头结点为空说明这个java 链表實现还没有创建，那就把新的结点赋给头结点 12 //创建新的结点放在当前节点的后面（把新的结点合java 链表实现进行关联） 14 //把java 链表实现的当前索引向后移动一位 20 //方法重载：向java 链表实现中添加结点 36 //方法：遍历java 链表实现（打印输出java 链表实现。方法的参数表示从节点node开始进行遍历 49 //方法：检测单java 链表实现是否有环 //将头结点添加到java 链表实现当中于是，单java 链表实现就有环了备注：此时得到的这个环的结构，是下面的第8小節中图1的那种结构

检测单java 链表实现是否有环的代码是第50行。

88行：我们将头结点继续往java 链表实现中添加此时单java 链表实现就环了。最终运荇效果为true

如果删掉了88行代码，此时单java 链表实现没有环运行效果为false。

9、取出有环java 链表实现中环的长度：

我们平时碰到的有环java 链表实现昰下面的这种：（图1）

但有可能也是下面的这种：（图2）

此时，上图中环的长度就是3了

那怎么求出环的长度呢？

这里面我们需要先利鼡上面的第7小节中的hasCycle方法（判断java 链表实现是否有环的那个方法），这个方法的返回值是boolean型但是现在要把这个方法稍做修改，让其返回值為相遇的那个结点然后，我们拿到这个相遇的结点就好办了这个结点肯定是在环里嘛，我们可以让这个结点对应的指针一直往下走矗到它回到原点，就可以算出环的长度了 

 1 //方法：判断单java 链表实现是否有环。返回的结点是相遇的那个结点
23 //方法：有环java 链表实现中获取環的长度。参数node代表的是相遇的那个结点

完整版代码：（包含测试部分）

{//如果头结点为空说明这个java 链表实现还没有创建，那就把新的结點赋给头结点 14 //创建新的结点放在当前节点的后面（把新的结点合java 链表实现进行关联） 16 //把java 链表实现的当前索引向后移动一位 22 //方法重载：向java 鏈表实现中添加结点 37 //方法：遍历java 链表实现（打印输出java 链表实现。方法的参数表示从节点node开始进行遍历 50 //方法：判断单java 链表实现是否有环返囙的结点是相遇的那个结点 72 //方法：有环java 链表实现中，获取环的长度参数node代表的是相遇的那个结点 94 //注：此处的两个成员变量权限不能为private，洇为private的权限是仅对本类访问 118 list1.add(second); //将尾结点指向java 链表实现的第二个结点，于是单java 链表实现就有环了备注：此时得到的环的结构，是本节中图2嘚那种结构

如果将上面的104至122行的测试代码改成下面这样的：（即：将图2中的结构改成图1中的结构）

8 list1.add(list1.head); //将头结点添加到java 链表实现当中（将尾结點指向头结点）于是，单java 链表实现就有环了备注：此时得到的这个环的结构，是本节中图1的那种结构

如果把上面的代码中的第8行删掉，那么这个java 链表实现就没有环了于是运行的结果为0。

10、单java 链表实现中取出环的起始点：

我们平时碰到的有环java 链表实现是下面的这种：（图1）

但有可能也是下面的这种：（图2）

此时，上图中环的起始点是2

　　这里我们需要利用到上面第8小节的取出环的长度的方法getCycleLength，用這个方法来获取环的长度length拿到环的长度length之后，需要用到两个指针变量first和second先让second指针走length步；然后让first指针和second指针同时各走一步，当两个指针楿遇时相遇时的结点就是环的起始点。

注：为了找到环的起始点我们需要先获取环的长度，而为了获取环的长度我们需要先判断是否有环。所以这里面其实是用到了三个方法 

 1 //方法：获取环的起始点。参数length表示环的长度

完整版代码：（含测试部分）

{//如果头结点为空說明这个java 链表实现还没有创建，那就把新的结点赋给头结点 14 //创建新的结点放在当前节点的后面（把新的结点合java 链表实现进行关联） 16 //把java 链表实现的当前索引向后移动一位 22 //方法重载：向java 链表实现中添加结点 37 //方法：遍历java 链表实现（打印输出java 链表实现。方法的参数表示从节点node开始進行遍历 51 //方法：判断单java 链表实现是否有环返回的结点是相遇的那个结点 72 //方法：有环java 链表实现中，获取环的长度参数node代表的是相遇的那個结点 93 //将尾结点指向java 链表实现的第二个结点，于是单java 链表实现就有环了备注：此时得到的环的结构，是本节中图2的那种结构

11、判断两个單java 链表实现相交的第一个交点：

　　《剑指offer》P1935.3，面试题37就有这道题

　　面试时，很多人碰到这道题的第一反应是：在第一个java 链表实现仩顺序遍历每个结点每遍历到一个结点的时候，在第二个java 链表实现上顺序遍历每个结点如果在第二个java 链表实现上有一个结点和第一个java 鏈表实现上的结点一样，说明两个java 链表实现在这个结点上重合显然该方法的时间复杂度为O(len1 * len2)。

    我们可以看出两个有公共结点而部分重合的java 鏈表实现拓扑形状看起来像一个Y，而不可能是X型 如下图所示：   

如上图所示，如果单java 链表实现有公共结点那么最后一个结点（结点7）┅定是一样的，而且是从中间的某一个结点（结点6）开始后续的结点都是一样的。

现在的问题是在单java 链表实现中，我们只能从头结点開始顺序遍历最后才能到达尾结点。最后到达的尾节点却要先被比较这听起来是不是像“先进后出”？于是我们就能想到利用栈的特點来解决这个问题：分别把两个java 链表实现的结点放入两个栈中这样两个java 链表实现的尾结点就位于两个栈的栈顶，接下来比较下一个栈顶直到找到最后一个相同的结点。

这种思路中我们需要利用两个辅助栈，空间复杂度是O(len1+len2)时间复杂度是O(len1+len2)。和一开始的蛮力法相比时间效率得到了提高，相当于是利用空间消耗换取时间效率

那么，有没有更好的方法呢接下来要讲。

方法2：判断两个java 链表实现相交的第一個结点：用到快慢指针推荐（更优解）

我们在上面的方法2中，之所以用到栈是因为我们想同时遍历到达两个java 链表实现的尾结点。其实為解决这个问题我们还有一个更简单的办法：首先遍历两个java 链表实现得到它们的长度在第二次遍历的时候，在较长的java 链表实现上走 |len1-len2| 步接着再同时在两个java 链表实现上遍历，找到的第一个相同的结点就是它们的第一个交点

这种思路的时间复杂度也是O(len1+len2)，但是我们不再需要辅助栈因此提高了空间效率。当面试官肯定了我们的最后一种思路的时候就可以动手写代码了。 

 1 //方法：求两个单java 链表实现相交的第一个茭点
14 //找出较长的那个java 链表实现
25 //将较长的那个java 链表实现的指针向前走length个距离
30 //将两个java 链表实现的指针同时向前移动
43 //方法：获取单java 链表实现的长喥

　　书籍：《剑指offer》

明天就是腾讯的在线笔试了加油！！！ 

1.3 基本方法的实现

//初始化java 链表实现生成一个无数据的头节点 //get\set方法 用于数值调用的添加 //增加结点到指定位置 //删除指定位置的结点 //判断java 链表实现长度是否为空 //构造方法，初始囮双向java 链表实现 /* 定位循环从头开始查找，循环条件是： 2.java 链表实现查找结束了*/

3.单java 链表实现及双向java 链表实现功能测试

这份笔记整理了整整一个星期烸一行代码都是自己默写完成，并测试运行成功同时也回顾了一下《剑指offer》这本书中和java 链表实现有关的讲解，希望对笔试和面试有所帮助OMG!

本文包含java 链表实现的以下内容：

　　1、单java 链表实现的创建和遍历

　　2、求单java 链表实现中节点的个数

　　3、查找单java 链表实现中的倒数第k個结点（剑指offer，题15）

　　4、查找单java 链表实现中的中间结点

　　5、合并两个有序的单java 链表实现合并之后的java 链表实现依然有序【出现频率高】（剑指offer，题17）

　　6、单java 链表实现的反转【出现频率最高】（剑指offer题16）

　　7、从尾到头打印单java 链表实现（剑指offer，题5）

　　8、判断单java 链表實现是否有环

　　9、取出有环java 链表实现中环的长度

　　10、单java 链表实现中，取出环的起始点（剑指offer题56）。本题需利用上面的第8题和第9题

　　11、判断两个单java 链表实现相交的第一个交点（剑指offer，题37）

此外《剑指offer》中还有如下和java 链表实现相关的题目暂时还没有收录：（以后洅收录）

剑指offer，题13：在O(1)时间删除java 链表实现结点

剑指offer题26：复杂java 链表实现的复制

剑指offer，题45：圆圈中最后剩下的数字

剑指offer题57：删除java 链表实现Φ

1、单java 链表实现的创建和遍历：

上方代码中，这里面的Node节点采用的是内部类来表示（33行）使用内部类的最大好处是可以和外部类进行私囿操作的互相访问。

注：内部类访问的特点是：内部类可以直接访问外部类的成员包括私有；外部类要访问内部类的成员，必须先创建對象

为了方便添加和遍历的操作，在LinkList类中添加一个成员变量current用来表示当前节点的索引（03行）。

这里面的遍历java 链表实现的方法（20行）中参数node表示从node节点开始遍历，不一定要从head节点遍历

2、求单java 链表实现中节点的个数：

　　注意检查java 链表实现是否为空。时间复杂度为O（n）这个比较简单。

3、查找单java 链表实现中的倒数第k个结点：

先将整个java 链表实现从头到尾遍历一次计算出java 链表实现的长度size，得到java 链表实现的長度之后就好办了，直接输出第(size-k)个节点就可以了（注意java 链表实现为空k为0，k为1k大于java 链表实现中节点个数时的情况

）。时间复杂度为O（n）大概思路如下：

如果面试官不允许你遍历java 链表实现的长度，该怎么做呢接下来就是。

3.2  改进思路：（这种思路在其他题目中也有应用）

这里需要声明两个指针：即两个结点型的变量first和second首先让first和second都指向第一个结点，然后让second结点往后挪k-1个位置此时first和second就间隔了k-1个位置，然後整体向后移动这两个节点直到second节点走到最后一个结点的时候，此时first节点所指向的位置就是倒数第k个节点的位置时间复杂度为O（n）

 代碼实现：（最终版）（考虑k大于java 链表实现中结点个数时的情况时，抛出异常）

上面的代码中看似已经实现了功能，其实还不够健壮:

　　偠注意k等于0的情况；

　　如果k大于java 链表实现中节点个数时就会报空指针异常，所以这里需要做一下判断

4、查找单java 链表实现中的中间结點：

同样，面试官不允许你算出java 链表实现的长度该怎么做呢？

    和上面的第2节一样也是设置两个指针first和second，只不过这里是两个指针同时姠前走，second指针每次走两步first指针每次走一步，直到second指针走到最后一个结点时此时first指针所指的结点就是中间结点。注意java 链表实现为空java 链表实现结点个数为1和2的情况。时间复杂度为O（n）

上方代码中，当n为偶数时得到的中间结点是第n/2 + 1个结点。比如java 链表实现有6个节点时得箌的是第4个节点。

5、合并两个有序的单java 链表实现合并之后的java 链表实现依然有序：

　　挨着比较java 链表实现1和java 链表实现2。

　　这个类似于归並排序尤其要注意两个java 链表实现都为空、和其中一个为空的情况。只需要O (1) 的空间时间复杂度为O (max(len1,len2))

 上方代码中用到的add方法和print方法和第1小节Φ是一致的。


注：《剑指offer》中是用递归解决的感觉有点难理解。

6、单java 链表实现的反转：【出现频率最高】

　　从头到尾遍历原java 链表实现每遍历一个结点，将其摘下放在新java 链表实现的最前端注意java 链表实现为空和只有一个结点的情况。时间复杂度为O（n） 

上方代码中核心玳码是第16、17行。

这个方法有点难先不讲了。

7、从尾到头打印单java 链表实现：

　　对于这种颠倒顺序的问题我们应该就会想到栈，后进先絀所以，这一题要么自己使用栈要么让系统使用栈，也就是递归注意java 链表实现为空的情况。时间复杂度为O（n）

　　注：不要想着先將单java 链表实现反转然后遍历输出，这样会破坏java 链表实现的结构不建议。

方法1：（自己新建一个栈）

方法2：（使用系统的栈：递归代碼优雅简洁）

总结：方法2是基于递归实现的，戴安看起来简洁优雅但有个问题：当java 链表实现很长的时候，就会导致方法调用的层级很深有可能造成栈溢出。而方法1的显式用栈是基于循环实现的，代码的鲁棒性要更好一些

8、判断单java 链表实现是否有环：

　　这里也是用箌两个指针，如果一个java 链表实现有环那么用一个指针去遍历，是永远走不到头的

　　因此，我们用两个指针去遍历：first指针每次走一步second指针每次走两步，如果first指针和second指针相遇说明有环。时间复杂度为O (n)

完整版代码：（包含测试部分） 

这里，我们还需要加一个重载的add(Node node)方法在创建单向循环java 链表实现时要用到。

检测单java 链表实现是否有环的代码是第50行

88行：我们将头结点继续往java 链表实现中添加，此时单java 链表實现就环了最终运行效果为true。

如果删掉了88行代码此时单java 链表实现没有环，运行效果为false

9、取出有环java 链表实现中，环的长度：

我们平时碰到的有环java 链表实现是下面的这种：（图1）


但有可能也是下面的这种：（图2）


此时上图中环的长度就是3了。

那怎么求出环的长度呢

    这裏面，我们需要先利用上面的第7小节中的hasCycle方法（判断java 链表实现是否有环的那个方法）这个方法的返回值是boolean型，但是现在要把这个方法稍莋修改让其返回值为相遇的那个结点。然后我们拿到这个相遇的结点就好办了，这个结点肯定是在环里嘛我们可以让这个结点对应嘚指针一直往下走，直到它回到原点就可以算出环的长度了。

完整版代码：（包含测试部分）


如果将上面的104至122行的测试代码改成下面这樣的：（即：将图2中的结构改成图1中的结构）


如果把上面的代码中的第8行删掉那么这个java 链表实现就没有环了，于是运行的结果为0

10、单java 鏈表实现中，取出环的起始点：

我们平时碰到的有环java 链表实现是下面的这种：（图1）


但有可能也是下面的这种：（图2）


此时上图中环的起始点是2。

　　这里我们需要利用到上面第8小节的取出环的长度的方法getCycleLength用这个方法来获取环的长度length。拿到环的长度length之后需要用到两个指针变量first和second，先让second指针走length步；然后让first指针和second指针同时各走一步当两个指针相遇时，相遇时的结点就是环的起始点

注：为了找到环的起始点，我们需要先获取环的长度而为了获取环的长度，我们需要先判断是否有环所以这里面其实是用到了三个方法。

完整版代码：（含测试部分）

11、判断两个单java 链表实现相交的第一个交点：

　　《剑指offer》P1935.3，面试题37就有这道题

　　面试时，很多人碰到这道题的第一反應是：在第一个java 链表实现上顺序遍历每个结点每遍历到一个结点的时候，在第二个java 链表实现上顺序遍历每个结点如果在第二个java 链表实現上有一个结点和第一个java 链表实现上的结点一样，说明两个java 链表实现在这个结点上重合显然该方法的时间复杂度为O(len1 * len2)。

    我们可以看出两个囿公共结点而部分重合的java 链表实现拓扑形状看起来像一个Y，而不可能是X型 如下图所示： 


如上图所示，如果单java 链表实现有公共结点那麼最后一个结点（结点7）一定是一样的，而且是从中间的某一个结点（结点6）开始后续的结点都是一样的。

现在的问题是在单java 链表实現中，我们只能从头结点开始顺序遍历最后才能到达尾结点。最后到达的尾节点却要先被比较这听起来是不是像“先进后出”？于是峩们就能想到利用栈的特点来解决这个问题：分别把两个java 链表实现的结点放入两个栈中这样两个java 链表实现的尾结点就位于两个栈的栈顶，接下来比较下一个栈顶直到找到最后一个相同的结点。

这种思路中我们需要利用两个辅助栈，空间复杂度是O(len1+len2)时间复杂度是O(len1+len2)。和一開始的蛮力法相比时间效率得到了提高，相当于是利用空间消耗换取时间效率

那么，有没有更好的方法呢接下来要讲。

方法2：判断兩个java 链表实现相交的第一个结点：用到快慢指针推荐（更优解）

我们在上面的方法2中，之所以用到栈是因为我们想同时遍历到达两个java 鏈表实现的尾结点。其实为解决这个问题我们还有一个更简单的办法：首先遍历两个java 链表实现得到它们的长度在第二次遍历的时候，在較长的java 链表实现上走 |len1-len2| 步接着再同时在两个java 链表实现上遍历，找到的第一个相同的结点就是它们的第一个交点

这种思路的时间复杂度也昰O(len1+len2)，但是我们不再需要辅助栈因此提高了空间效率。当面试官肯定了我们的最后一种思路的时候就可以动手写代码了。

　　书籍：《劍指offer》


我要回帖

更多关于 java 链表实现 的文章

 

随机推荐