18 删除链表的节点

这道题牛客和《剑指offer》不一样

《剑指offer》：给定单项链表的头指针和一个节点的指针，在 O(1) 时间内删除该节点。

当这个节点不是最后一个节点，可以在 o(1) 时间找到这个节点，把下一个节点的值赋给它，然后删除下一个节点。如果是最后一个节点，只能从头遍历，时间复杂度 o(n)

public void deletNode(ListNode head, ListNode toBeDeleted){
    if(toBeDeleted.next!=null){
        toBeDeleted.val = toBeDeleted.next.val;
        ListNode t=toBeDeleted.next.next;
        toBeDeleted.next = null;
        toBeDeleted.next = t;
    } else if (head == toBeDeleted){ //只有一个节点
        return null;
    } else { 
        //最后一个节点
        ListNode p=head;
        while(p.next!=toBeDeleted){
            p=p.next;
        }
        p.next=null;
    }
}

牛客改为删除某个值的节点，没有指针

public ListNode deleteNode (ListNode head, int val) {
    if(val==head.val) return head.next;
    ListNode p=head;
    while(p.next.val!=val){
        p=p.next;
    }
    ListNode t=p.next.next;
    p.next.next=null;
    p.next=t;
    return head;
}

删除链表的重复节点

牛客

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead==null) return null;
        ListNode ret = new ListNode(-1);
        ret.next=pHead;
        ListNode p = ret;
        ListNode t=p.next;
        while(p!=null && p.next!=null){
            t=p.next;
            if(t.next!=null && t.val==t.next.val){
                while(t.next!=null && t.val == t.next.val){
                    t=t.next;
                }
                t=t.next;
                p.next=t;
            } else {
                p=p.next;
            }
        }
        return ret.next;
    }
}