剑指 Offer 18. 删除链表的节点

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

返回删除后的链表的头节点。

JAVA

package leetcode;

public class ListNode {
     public int val;
     public  ListNode next;
     public  ListNode(int x){
         val=x;
         next=null;
     }
     public static ListNode deleteNode(ListNode head,ListNode tobedeleted){
         if(head==null|| tobedeleted==null) {
             System.out.println("头节点或者被删节点为空");
             return head;
         } ;
         //删除节点位于中间
         if(tobedeleted.next!=null){
             tobedeleted.val=tobedeleted.next.val;
             tobedeleted.next=tobedeleted.next.next;
         }
         //删除节点是头节点，链表只有一个节点
         else if(head==tobedeleted){
             head=null;
         }else{
             //删除尾节点,从头开始遍历找尾戒点的前一个节点
             ListNode cur=head;
             while(cur.next!=tobedeleted){
                 cur=cur.next;
             }
             cur.next=null;
         }
         return  head;
     }
     public  static void  printList(ListNode head){
         ListNode cur=head;
         while(cur!=null){
             System.out.print(cur.val+" ");
             cur=cur.next;
         }
         System.out.println();

     }

    public static void main(String[] args) {
        ListNode one=new ListNode(1);
        ListNode two=new ListNode(2);
        ListNode three = new ListNode(3);
        ListNode four=new ListNode(4);
        ListNode five=new ListNode(5);
        ListNode six=new ListNode(6);
        one.next=two;
        two.next=three;
        three.next=four;
        four.next=five;
        five.next=six;
        System.out.println("初始化后链表：");
        ListNode.printList(one);
        //删除空节点
        System.out.println("删除空节点：");
        ListNode head=one;
        head=ListNode.deleteNode(head,null);

        ListNode.printList(head);
        System.out.println("删除中间节点：");
        head=ListNode.deleteNode(head,four);
        ListNode.printList(head);
        System.out.println("删除尾节点：");
        head=ListNode.deleteNode(head,six);
        ListNode.printList(head);
        System.out.println("删除头节点：");
        head=ListNode.deleteNode(head,head);
        ListNode.printList(head);
    }
}

测试

初始化后链表：
1 2 3 4 5 6 
删除空节点：
头节点或者被删节点为空
1 2 3 4 5 6 
删除中间节点：
1 2 3 5 6 
删除尾节点：
1 2 3 5 
删除头节点：
2 3 5 

Process finished with exit code 0

扩展
一个排序链表，删除重复的节点。
1>2>2>4>4>6
删除后 1>6

java

package leetcode;

public class ListNode {
     public int val;
     public  ListNode next;
     public  ListNode(int x){
         val=x;
         next=null;
     }
  
     public  static void  printList(ListNode head){
         ListNode cur=head;
         while(cur!=null){
             System.out.print(cur.val+" ");
             cur=cur.next;
         }
         System.out.println();

     }
     public static  ListNode deleteDuplication(ListNode head){
         /*
         * 1->2>2>3
         * 删除重复节点后
         * 1->3
         * */
         //空链表
         if(head==null)
         {
             return head;
         }
         //需要遍历链表， 设置前置游标和当前游标
         ListNode  pre=null;
         ListNode cur=head;
         while (cur!=null){
             //判断当前节点的下一个节点是否和当前相同
             ListNode pnext=cur.next;
             boolean needDelete=false;
             if(pnext!=null && pnext.val==cur.val){
                 needDelete=true;
             }
                    //若当前节点的下一个节点和当前节点不相同
             if(!needDelete){
                  pre=cur;
                  cur=cur.next;
             }else{
                 int val= cur.val;
                 ListNode tobedelete=cur;
                 while (tobedelete!=null && tobedelete.val==val){
                     pnext=tobedelete.next;
                     tobedelete=pnext; }
             }
             //头节点也被删除的情况
             if(pre==null){
                 head=pnext;
             }
             else{
                 pre.next=pnext;
             }
             cur=pnext;
         }
         return head;
     }

    public static void main(String[] args) {
        ListNode one=new ListNode(1);
        ListNode two=new ListNode(2);
        ListNode three = new ListNode(2);
        ListNode four=new ListNode(4);
        ListNode five=new ListNode(4);
        ListNode six=new ListNode(6);
        one.next=two;
        two.next=three;
        three.next=four;
        four.next=five;
        five.next=six;
        ListNode head=one;
        System.out.println("初始化后链表：");
        ListNode.printList(head);
        System.out.println("删除重复节点后链表：");
        head=ListNode.deleteDuplication(head);
        ListNode.printList(head);

    }
}

结果

初始化后链表：
1 2 2 4 4 6 
删除重复节点后链表：
1 6 

Process finished with exit code 0