剑指offer 18：删除链表的节点

小半 • 2023年2月3日上午10:54 • 技术随笔 • 阅读 169

题目：
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

1.此题对比原题有改动
2.题目保证链表中节点的值互不相同
3.该题只会输出返回的链表和结果做对比，所以若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

方法一：双指针

首先校验，若为head为null则返回null
若要删除的是head，则返回head.next
双指针遍历链表，找出要删除的节点并删掉
若遍历到结尾还没有，则返回null
（while+if）

public class Solution {
    public ListNode deleteNode (ListNode head, int val) {
        if(head==null){//校验
            return null;
        }
        //判断要删除的是否头节点
        if(head.val==val){
            return head.next;
        }
        //双指针
        ListNode pre=null;
        ListNode curr=head; 
        while(curr!=null){
            if(curr.val==val){ //若找到要删除的，删除后直接return头节点
                pre.next=curr.next;
                return head;
            }
            pre=curr;
            curr=curr.next;
        }
        //若循环到最后还没有出现要删除的，则返回null，此时curr=null
        return curr;
    }
}

方法二：使用伪节点、双指针

使用伪节点的next来作为指针，在遇到“要删除的是头节点”这种情况时不需要去特殊处理。
使用curr.next作为指针，一旦发现curr.next是要删除的结点，使得curr.next=curr.next.next即可。
注意：
当出现xx.next.next时，小心空指针异常，while条件中光有xx.next!=null是不够的，还要有xx.next.next!=null ！！！

public class Solution {
    public ListNode deleteNode (ListNode head, int val) {
        if(head==null){ //首先校验
            return null;}
        //双指针
        ListNode mer=new ListNode(-1);    //伪节点
        mer.next=head;
        ListNode curr=mer;
        //用伪节点时，可以更容易处理 head为要删除的结点这种情况
        while(curr.next!=null){ // while+if !
            if(curr.next.val==val){
                curr.next=curr.next.next;//删除结点，然后即可跳出循环
                break;
            }else{ //若不是要删除的元素，则指针后移。
                curr=curr.next;
            }            
        }
        return mer.next;
    }
}