快慢指针
鲁米诺反应-社区医学
2023年2月22日发(作者：八卦五行属性对照表)单链表常⽤算法
⽂章⽬录
单链表
单链表是⼀种包含⼀个指向后继节点的指针和数据域
/**
*节点类
*/
publicclassListNode{
intval;
ListNodenext;
ListNode(intx){val=x;}
}
单链表经典算法题
1.删除链表中等于给定值val的所有节点。
⽰例:
输⼊:1->2->6->3->4->5->6,val=6
输出:1->2->3->4->5
直接操作链表
/**
*删除链表中指定值的节点--->【双指针】
*@paramhead
*@paramval
*@return
*/
publicListNoderemoveElements(ListNodehead,intval){
if(head==null){
returnnull;
}
//要删除的是第⼀个节点
while(==val){
head=;
if(head==null){
returnnull;
}
}
//其他情况
//当前指针，指向当前节点
ListNodecurNode=;
//前驱指针，指向当前节点的前驱节点
ListNodepreNode=head;
while(curNode!=null){
if(==val){
//前节点的后继节点变成当前节点的后继节点
=;
curNode=;
}else{
preNode=;
curNode=;
}
}
returnhead;
}
递归解法
/**
*删除链表中指定值的节点--->【递归】
*@paramhead
*@paramval
*@return
*/
publicListNoderemoveElements2(ListNodehead,intval){
if(head!=null){
=removeElements(,val);
==val?:head;
}
returnhead;
}
2.返回链表的中间节点
给定⼀个带有头结点head的⾮空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第⼆个中间结点。
快慢指针
/**
*返回链表的中间节点---->【快慢指针】
*@paramhead
*@return
*/
publicListNodemiddleNode(ListNodehead){
if(head==null||==null){
returnhead;
}
ListNodeslow=head;
ListNodefast=head;
while(fast!=null&&!=null){
fast=;
slow=;
}
returnslow;
}
计算链表长度，然后返回从中间节点开始的序列
/**
*返回链表的中间节点---->【计算链表长度，然后返回从中间节点开始的序列】
*@paramhead
*@return
*/
publicListNodemiddleNode2(ListNodehead){
intlen=0;
ListNodeq=head;
while(q!=null){
len++;
q=;
}
inttemp=0;
ListNodenode=head;
while(node!=null){
temp++;
if(temp==len/2+1){
break;
}
node=;
}
returnnode;
}
3.删除指定节点
/**
*删除指定节点(单链表)--->【直接覆盖】
*时间复杂度：O(1)
*空间复杂度：O(1)
*@paramnode
*/
publicvoiddeleteNode(ListNodenode){
//后继节点覆盖node
=;
=;
}
4.删除链表中的重复元素
/**
*删除链表中的重复元素(单链表)【单指针】
*时间复杂度：O(N)
*空间复杂度：O(1)
*@paramhead
*@return
*/
publicListNodedeleteDuplicates(ListNodehead){
if(head==null){
returnnull;
}
//有序链表直接遍历即可
ListNodenode=head;
while(!=null){
if(==){
=;
}else{
node=;
}
}
returnhead;
}
5.反转链表
迭代
/**
*反转链表【迭代】
*@paramhead
*@return
*/
publicListNodereverseList(ListNodehead){
ListNodenewHead=null;
ListNodeh=head;
while(h!=null){
ListNodetmp=;
=newHead;
newHead=h;
h=tmp;
}
//pre:每次指向反转链表的头结点
returnnewHead;
}
递归
/**
*反转链表【递归】
*@paramhead
*@return
*/
publicListNodereverseList2(ListNodehead){
if(head==null||==null){
returnhead;
}
ListNodenewHead=reverseList();
//反转过程
=head;
=null;
returnnewHead;
}
6.删除倒数第n个节点
/**
*删除倒数第n个节点
*@paramhead
*@paramn
*@return
*/
publicListNoderemoveNthNode(ListNodehead,intn){
if(head==null||==null){
returnnull;
}
ListNodenode=newListNode(-1);
ListNodeslow=head;
ListNodefast=head;
for(inti=0;i fast=; } while(fast!=null){ fast=; slow=; } =; ; }