本文转载自微信公众号《程序员千语》，作者程序员千语。转载本文请联系J程序员钱宇公众号。Leetcode：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof“GitHub：https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_12_hammingWeight/Solution.java删除链表的节点》题目描述：给定单向链表的头指针和要删除的节点的值,定义一个删除节点的函数.返回被删除链表的头节点.例1:输入:head=[4,5,1,9],val=5输出:[4,1,9]解释:给定你的链表中值为5的第二个节点，那么你调用函数后，链表应该变为4->1->9。示例2：输入：head=[4,5,1,9],val=1输出：[4,5,9]解释：给定你的链表中的第三个节点值为1，那么在调用你的函数后，链表应该变为4->5->9解题思路：本题需要分两步删除一个值为val的节点：定位节点，修改ref诚恳。定位节点：遍历链表直到head.val==val跳出定位目标节点。修改引用：设节点cur的前驱节点为pre，后继节点为cur.next；执行pre.next=cur.next删除cur节点。**算法流程：**特例处理：当头节点head需要删除时，直接返回head.next即可。初始化：pre=head，cur=head.next。定位节点：当cur为空或者cur节点的值等于val时跳出。保存当前节点索引，即pre=cur。遍历下一个节点，即cur=cur.next。删除节点：如果cur指向一个节点，执行pre.next=cur.next;如果cur指向null，则表示链表不包含值为val的节点。返回值：只返回链表的头节点head。复杂度分析：时间复杂度O(N)：N是链表的长度，删除操作平均需要循环N/2次，最差的是N次。空间复杂度O(1):cur,pre占用恒定大小的额外空间。packagecom.nateshao.sword_offer.topic_15_deleteNode;/***@dateCreatedby邵通杰on2021/11/2116:22*@微信公众号程序员千语*@个人网站www.nateshao.cn*@bloghttps://nateshao.gitee.io*@GitHubhttps://github.com/nateshao*@Giteehttps://gitee.com/nateshao*说明：删除链表的节点*/publicclassSolution{publicstaticvoidmain(String[]args){ListNodelistNode=newListNode(3);intval=3;ListNodenode=deleteNode(listNode,val);System.out.println("node="+node);}//推荐publicstaticListNodeleteNode(ListNodehead,intval){if(head.val==val)returnhead.next;ListNodepre=head,cur=head.next;while(cur!=null&&cur.val!=val){pre=cur;cur=cur.next;}if(cur!=null)pre.next=cur.next;returnhead;}??publicvoiddeleteNode(ListNodehead,ListNodedeListNode){if(deListNode==null||head==null)return;if(head==deListNode){head=null;}else{//如果删除的节点是结尾节点，往后移一个if(deListNode.next==null){ListNodepointListNode=head;while(pointListNode.next.next!=null){pointListNode=pointListNode.next;}pointListNode.next=null;}else{deListNode.val=deListNode.next.val;deListNode.next=deListNode.next.next;}}}/***单指针实现**@paramhead*@paramval*@return*/publicListNodedeleteNode2(ListNodehead,intval){if(head==null)returnnull;if(head.val==val)returnhead.next;ListNodecur=head;while(cur.next!=null&&cur.next.val!=val){cur=cur.next;}if(cur.next!=null){cur.next=cur.next.next;}returnhead;}??/***递归现实**@paramhead*@paramval*@return*/publicListNodedeleteNode3(ListNodehead,intval){if(head==null)returnnull;if(head.val==val)returnhead.next;elsehead.next=deleteNode3(head.next,val);returnhead;}??publicstaticclassListNode{intval;ListNodenext;ListNode(intx){val=x;}}}参考链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/solution/mian-shi-ti-18-shan-chu-lian-biao-德捷电sh-2
