Java如何实现一个单向非循环链表

这篇文章主要介绍“Java如何实现一个单向非循环链表”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“Java如何实现一个单向非循环链表”文章能帮助大家解决问题。

1、什么是链表？

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

通俗点，就是每个元素是一个节点，然后用一个指针域给后面的节点连起来，第一个节点没有前驱，最后一个节点没有后继。

实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向、双向 2. 带头、不带头 3. 循环、非循环

我们重点讲解单向非循环链表和双向非循环链表，同时这两个也是笔试中考的比较多的。

2、实现一个单向非循环链表

2.1 实现前的约定

因为链表的每个元素是一个节点，所以我们采取内部类的方式，而我们还需要定义一个头节点的引用，来始终指向头节点。

publicclassMySingleList{privateListNodehead;//引用头节点//链表每个元素是一个节点privateclassListNode{privateintval;//存放数据元素privateListNodenext;//存放下一个节点地址//构造方法publicListNode(intval){this.val=val;}}}

注意：链表最少有两个域，分别是数据域和指针域，当然你也可以有多个数据域和指针域。

我们还需要实现以下几个常用的方法：

publicvoidaddFirst(intdata);//头插法publicvoidaddLast(intdata);//尾插法publicbooleanaddIndex(intindex,intdata);//任意位置插入,第一个数据节点为0号下标publicbooleancontains(intkey);//查找关键字key是否在单链表当中publicvoidremove(intkey);//删除第一次出现关键字为key的节点publicvoidremoveAllKey(intkey);//删除所有值为key的节点publicintsize();//得到单链表的长度publicvoidclear();//清空链表

2.2 addFirst 方法

publicvoidaddFirst(intdata){ListNodenewNode=newListNode(data);//把传过来的值放到新的节点中newNode.next=this.head;//新节点的next指向头节点this.head=newNode;//使新节点成为头节点}

因为head默认是指向空的，当链表为null，也不影响这个代码的执行，不信你下来画画图咯。


2.3 addList 方法

publicvoidaddLast(intdata){ListNodenewNode=newListNode(data);//如果链表为空的情况if(this.head==null){this.head=newNode;return;}//先找到最后一个节点ListNodecur=this.head;while(cur.next!=null){cur=cur.next;}cur.next=newNode;}

2.4 addIndex 方法

//任意位置插入,第一个数据节点为0号下标privateListNodefindIndexPrevNode(intindex){ListNodecur=this.head;while(index-1!=0){cur=cur.next;index--;}returncur;}publicbooleanaddIndex(intindex,intdata){//判断index下标的有效性if(index<0||index>size()){returnfalse;}//如果在0下标插入则是头插if(index==0){addFirst(data);//头插returntrue;}//如果在末尾插入则是尾插if(index==size()){addLast(data);//尾插returntrue;}ListNodenewNode=newListNode(data);//新节点//在中间插入ListNodeprevNode=findIndexPrevNode(index);//找到index下标的前一个节点newNode.next=prevNode.next;//新节点的next被改为index的位置的节点prevNode.next=newNode;//index位置前一个节点next被改成新节点returntrue;}

这个代码我们首先需要找到index下标的前一个节点，先让新节点跟index位置的节点绑定起来，在把index的前一个节点与新节点连起来，这个地方说文字是不清楚的，小伙伴们可以下来按照我这个代码画图就能理解了，也可也直接看博主之前的C语言实现数据结构专栏，那里面有图解哈。

2.5 contains 方法

//查找关键字key是否在单链表当中publicbooleancontains(intkey){//当链表为空的情况if(this.head==null){returnfalse;}ListNodecur=this.head;//遍历列表while(cur!=null){if(cur.val==key){returntrue;//找到了返回true}cur=cur.next;}returnfalse;//找不到返回false}

思路很简单，遍历一遍链表，找到 cur 为空位置，如果有返回true，没有返回false，交给小伙伴自己下来画图咯。

2.6 remove 方法

//删除第一次出现关键字为key的节点publicvoidremove(intkey){if(this.head==null){return;}ListNodecur=this.head;//如果删除的是key为头节点if(this.head.val==key){this.head=head.next;return;}//这里不能是cur!=null,不然会越界！！！while(cur.next!=null){//找到key的前一个节点if(cur.next.val==key){//当前的cur为key的前一个节点cur.next=cur.next.next;//cur链接到key的后一个节点return;}cur=cur.next;}}

这里我们需要找到key的前一个节点，然后进行跟key后面的节点绑定即可，当key对应节点没人引用了，则会被自动回收掉。

2.7 removeAllKey 方法

//删除所有值为key的节点publicvoidremoveAllKey(intkey){if(this.head==null){return;}//采用前后指针的方法ListNodecur=this.head;ListNodeprev=this.head;while(cur!=null){if(cur.val==key){prev.next=cur.next;//跳过key节点指向下一个节点}else{prev=cur;}cur=cur.next;}//判断第一个节点是不是keyif(this.head.val==key){this.head=this.head.next;//head指向下一个节点}}

这里大家伙先自己看看，后面讲解OJ题会有这道题详解的。

2.8 size 和 clear 方法

我相信这两个方法就不需要多说了吧？遍历？直接头指针置null？这不就简单了吗，这里就不写了哈，交给各位了！

3、单链表OJ题深度解剖

这个才是今天的重头戏，不是篮球哥不画图，是因为前面的图太简单了，小伙伴们结合着代码也能自己画出来，但是，对于OJ题，大家伙下去还是得画图的，相信看完这几道题，你会爱上数据结构的。

3.1 移除链表元素(来源:LeetCode 难度:简单)

题目：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

这个题我们可以用前后指针的思路来做，这样也比较通俗易懂，更适合初学者，大概的思路是这样的：我们可以定义一个cur和first的引用，如果碰到相等，也就是first.val == val，我们则让cur的next指向first的下一个节点，如果不相等，则让cur走到first的位置，最后first往后走一步，图解：

这里还没有完，如果第一个节点的值也是val呢？所以最后我们别忘了进行一个判断，那么最终的代码是这样的：

publicListNoderemoveElements(ListNodehead,intval){if(head==null){returnnull;}ListNodecur=head;ListNodefirst=head;while(first!=null){if(first.val==val){cur.next=first.next;}else{cur=first;}first=first.next;}//判断头节点的值是否也是valif(head.val==val){head=head.next;}returnhead;}

3.2 反转链表(来源:LeetCode 难度:简单)

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

这个题我们可以先取到头节点，后续的节点都进行头插法即可？我们取到头节点，并且先将头节点的next置空，但是这样一来，就找不到后面的节点了，所以我们还需要有一个curNext引用来记录要反转节点的下一个节点：

我们的思路是这样的：首先找到头节点的next置空，cur走到curNext位置，curNext往前走，使得cur位置的next指向头节点，头节点cur再次成为新的头节点，当curNext走到null的时候循环结束。

publicListNodereverseList(ListNodehead){//空链表的情况if(head==null){returnnull;}ListNodecur=head;ListNodecurNext=cur.next;head.next=null;while(curNext!=null){cur=curNext;curNext=curNext.next;cur.next=head;head=cur;}returnhead;}

3.4 链表中倒数第k个节点

题目：输入一个链表，输出该链表中倒数第k个结点。

这个题也是很简单的一道题，可以采用前后指针法，先让first指针走k步，走完之后slow和first一起走，这样slow和first之间就相差了k步，当first为null时，slow就是倒数第k个节点，在这个过程中，我们还要判断k的合法性，如果k小于等于0？或者k大于链表的长度呢？于是我们就能写出如下的代码：

publicListNodeFindKthToTail(ListNodehead,intk){//判断k的合法性if(k<=0||head==null){returnnull;}ListNodefirst=head;ListNodeslow=head;//先让first走k步while(k!=0){//k的长度大于链表的长度if(first==null){returnnull;}first=first.next;k--;}//一起走,当first为null,slow就是倒数第k个节点while(first!=null){first=first.next;slow=slow.next;}returnslow;}

3.6 链表分割(来源:牛客网 难度:较难)

题目：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

这个题的思路我们可以这样做，既然是按照给定的值x进行分割，那么我们设定两个盘子，盘子A放小于x的节点，盘子B放大于x的节点，最后把这两个盘子的节点连起来，放回盘子A的头节点即可！

publicListNodepartition(ListNodepHead,intx){if(pHead==null){returnnull;}ListNodeheadA=null;ListNodeheadB=null;ListNodecurA=null;ListNodecurB=null;ListNodecur=pHead;while(cur!=null){if(cur.val<x){//第一次放入A盘子if(headA==null){headA=cur;curA=cur;}else{curA.next=cur;curA=cur;}}else{//第一次放入B盘子if(headB==null){headB=cur;curB=cur;}else{curB.next=cur;curB=cur;}}cur=cur.next;}//如果A盘子为空if(headA==null){returnheadB;}curA.next=headB;//避免B盘子尾节点形成环if(headB!=null){curB.next=null;}returnheadA;}

3.7 链表的回文结构(来源:LeetCode 难度:较难)

题目：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

这个题有要求的，要求空间复杂度为O(1)，并且还得在O(n)的时间复杂度下，那我们就原地解决这个题，我们可以分为三个步骤，首先找到中间节点，然后把中间节点往后的节点进行反转，最后左右两个指针同时往中间走。如果光看下面代码看不懂，可以结合着代码画图才能理解更透彻哦！

publicbooleanchkPalindrome(ListNodeA){if(A==null){returnfalse;}//只有一个节点的情况if(A.next==null){returntrue;}//首先找到中间节点ListNodefirst=A;ListNodeslow=A;while(first!=null&&first.next!=null){first=first.next.next;slow=slow.next;}//走到这,slow是链表的中间节点,采用头插法反转slow后续的节点first=slow.next;ListNodecur=slow;while(first!=null){cur=first;first=first.next;cur.next=slow;//链接前一个节点slow=cur;//更新头节点的位置}//走到这,反转完毕,cur指向最后一个节点,让slow等于A,往中间找slow=A;while(slow!=cur){if(slow.val!=cur.val){returnfalse;}//偶数的情况下需要特殊判断if(slow.next==cur){returntrue;}slow=slow.next;cur=cur.next;}returntrue;}

3.8 相交链表(来源:LeetCode 难度:简单)

题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

这个题我们可以这样做，长链表先走两个链表的长度差的步数，因为相交之后的节点都是一样的个数，所以走了差值后，就两个链表一起往后走，相等了则就是相交节点。

publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){if(headA==null||headB==null){returnnull;}ListNodelongList=headA;//longList始终记录长的链表ListNodeshortList=headB;//分别求出两个链表的长度intlenA=0;intlenB=0;ListNodecur=headA;while(cur!=null){lenA++;cur=cur.next;}cur=headB;while(cur!=null){lenB++;cur=cur.next;}intlen=lenA-lenB;//如果B链表长于A链表if(len<0){//修正相差长度len=lenB-lenA;longList=headB;//longList始终记录长的链表shortList=headA;}//让长链表先走差值len步,然后同步走,相等了即为相交节点while(len!=0){longList=longList.next;len--;}while(longList!=shortList){longList=longList.next;shortList=shortList.next;}//如果两个链表走到了null,则没有中间节点返回null,如果有,返回任意一个即可returnlongList;}

关于“Java如何实现一个单向非循环链表”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识，可以关注主机评测网行业资讯频道，小编每天都会为大家更新不同的知识点。

上一篇：php购物增加减少功能如何实现

下一篇：CSS渐变锯齿问题怎么解决

---