Java如何实现一个单向非循环链表(java,编程语言)

！！
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;
}
//判断第一个节点是不是key
if(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;
}
//判断头节点的值是否也是val
if(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如何实现一个单向非循环链表”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识，可以关注亿速云行业资讯频道，小编每天都会为大家更新不同的知识点。