链表Linked List-链表删除 Deletion in Linked List（5）

Love The Way You Lie 2023-09-24 19:24 71阅读 0赞

# 1.从头中尾删除元素 #

You can delete an element in a list from:

*  Beginning
 *  Middle
 *  End

## 1）从头删除元素 ##

> Input : 1 -> 2 -> 3 -> 4 -> 5 -> NULL  
> Output : 2 -> 3 -> 4 -> 5 -> NULL

> Input : 2 -> 4 -> 6 -> 8 -> 33 -> 67 -> NULL  
> Output : 4 -> 6 -> 8 -> 33 -> 67 -> NULL

### Steps: ###

要删除第一个节点，我们需要使第二个节点成为头节点并删除为第一个节点分配的内存

### 代码 ###

class LinkedList {
        
        static ListNode head;
        public static ListNode deleteNode(ListNode head){
        
            if (head == null)
                return null;
            // 将头指针移动到下一个节点
            ListNode temp = head;
            head = head.next;
    
            return head;
        }
        
        /*或者使用以下方法，解题思路基本相同
        public static ListNode deleteNode(ListNode head){
            ListNode temp =null;
           if(head==null) {//检查列表是否为空
               return null;
           }else{//检查列表是否只包含一个节点
               if(head != temp) {///如果不是，head 将指向列表中的下一个节点，temp 将指向新的 head。
                   head = head.next;
               }else{//如果列表只包含一个节点
                   head=temp=null;//然后，它将删除它并且头和尾都将指向 null
               }
    
           }
           return head;
        }
        * */
        public static void push(int new_data) {
        
            ListNode new_node = new ListNode(new_data);
            new_node.next = head;
            head = new_node;
        }
        public void print(){
        
            ListNode node = head;
            while(node!=null){
        
                System.out.print(node.val+" ");
                node = node.next;
            }
    
        }
        public static void main (String[]args){
        
            LinkedList list = new LinkedList();
            list.push(1);
            list.push(3);
            list.push(8);
            list.push(4);
            System.out.println("\nCreated Linked list is:");
            list.print();
    
            head=deleteNode(head);
            System.out.println(
                    "\nLinked List after Deletion middle node:");
            list.print();
    
        }
        static class ListNode {
        
            int val;
            ListNode next;
            ListNode(int value){
        
                val = value;
                next=null;
            }
        }
    }

Created Linked list is:
    4 8 3 1 
    Linked List after Deletion middle node:
    8 3 1

## 2）从中间删除元素 ##

> Input: 1->2->3->4->5  
> Output: 1->2->4->5

> Input: 1->2->3->4->5 >6  
> Output: 1->2->3->5->6

### 简单的解题方法： ###

### Steps: ###

1.  给定一个单向链表，删除链表的中间部分。比如给定的链表是1->2->3->4->5那么链表应该修改为1->2->4->5
2.  如果有偶数个节点，则中间有两个节点，我们需要删除第二个中间元素。例如，如果给定的链表是 1->2->3->4->5->6 那么它应该修改为 1->2->3->5->6。
3.  如果输入链表为 NULL，那么它应该保持为 NULL。
4.  如果输入链表有1个结点，则删除该结点，返回新的头

简单的解决方案：想法是首先计算链表中的节点数，然后使用简单的删除过程删除第 n/2 个节点。

`Time Complexity`: `O(n)`.  
Two traversals of the linked list are needed  
`Auxiliary Space`: `O(1)`.  
No extra space is needed.

### 代码 ###

class LinkedList {
        
        static ListNode head;
    
        static int countOfNodes(ListNode head){
        //数结点个数
            int count=0;
            while(head!=null){
        
                head=head.next;
                count++;
            }
            return  count;
        }
        public static ListNode deleteNode(ListNode head){
        // 删除中间节点并返回
           if(head==null||head.next==null) return null;
           ListNode res=head;
           int count= countOfNodes(res);
           int mid=count/2;
           while(mid-->1){
        
               head=head.next;
           }
           head.next=head.next.next;
           return res;
        }
        public static void push(int new_data) {
        
            ListNode new_node = new ListNode(new_data);
            new_node.next = head;
            head = new_node;
        }
        public void print(){
        
            ListNode node = head;
            while(node!=null){
        
                System.out.print(node.val+" ");
                node = node.next;
            }
        }
       public static void main (String[]args){
        
            LinkedList list = new LinkedList();
            list.push(1);
            list.push(3);
            list.push(8);
            list.push(4);
            System.out.println("\nCreated Linked list is:");
            list.print();
    
            deleteNode(head);
            System.out.println(
                    "\nLinked List after Deletion middle node:");
            list.print();
    
        }
        static class ListNode {
        
            int val;
            ListNode next;
            ListNode(int value){
        
                val = value;
                next=null;
            }
        }
    
    }

Created Linked list is:
    4 8 3 1 
    Linked List after Deletion middle node:
    4 8 1

### 高效的解题方法： ###

上述解决方案需要对链表进行两次遍历。中间节点可以使用一次遍历删除。

### Steps: ###

1.  使用两个指针，slow\_ptr 和 fast\_ptr。
2.  两个指针都从列表的头部开始。当 fast\_ptr 到达末尾时，slow\_ptr 到达中间。
3.  跟踪前一个中间节点，以便可以删除中间节点。

### 代码 ###

class LinkedList {
        
        static ListNode head;
       
        public static ListNode deleteNode(ListNode head){
        // 删除中间节点并返回
           if(head==null&&head.next==null) return null;
            ListNode slow_ptr = head;//初始化慢指针和快指针, 到达链表的中间
            ListNode fast_ptr = head;
            ListNode pre=null;//找到中间的中间和前面的
            //存储 slow_ptr 的前一个
            while(fast_ptr!=null&&fast_ptr.next!=null){
        
                fast_ptr=fast_ptr.next.next;
                pre=slow_ptr;
                slow_ptr=slow_ptr.next;
            }
            pre.next=slow_ptr.next;//删除中间节点
            return head;
    
        }
        public static void push(int new_data) {
        
            ListNode new_node = new ListNode(new_data);
            new_node.next = head;
            head = new_node;
        }
        public void print(){
        
            ListNode node = head;
            while(node!=null){
        
                System.out.print(node.val+" ");
                node = node.next;
            }
    
        }
        public static void main (String[]args){
        
            LinkedList list = new LinkedList();
            list.push(1);
            list.push(3);
            list.push(8);
            list.push(4);
            System.out.println("\nCreated Linked list is:");
            list.print();
    
            deleteNode(head);
            System.out.println(
                    "\nLinked List after Deletion middle node:");
            list.print();
    
        }
        static class ListNode {
        
            int val;
            ListNode next;
            ListNode(int value){
        
                val = value;
                next=null;
            }
        }
    }

Created Linked list is:
    4 8 3 1 
    Linked List after Deletion middle node:
    4 8 1

## 3）从尾部删除元素 ##

> Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL  
> Output: 1 -> 2 -> 3 -> 4 -> NULL  
> ![在这里插入图片描述][70ab2350756844a2a95b30cdcb391368.gif_pic_center]  
> `Time Complexity`: `O(n)`.  
> The algorithm involves traversal of the linked list till its end, so the time complexity required is O(n).  
> `Space Complexity`: `O(1)`.  
> No extra space is required, so the space complexity is constant.

### Steps： ###

处理方法：要删除链表的最后一个节点，找到倒数第二个节点并使该节点的next指针为空。

1.  如果第一个节点为空或只有一个节点，则它们返回空。  
    如果 headNode == null 则返回 null  
    如果 headNode.nextNode == null 然后释放  
    头并返回空
2.  创建一个额外的空间secondLast，并遍历链表直到倒数第二个节点  
    当secondLast.nextNode.nextNode != null  
    secondLast = secondLast.nextNode
3.  删除最后一个节点，即delete(secondLast.nextNode)的倒数第二个节点的下一个节点，并将下一个倒数第二个节点的值设置为null。

### 代码 ###

package com.amy;
    
    
    import static java.util.Collections.sort;
    
    /**
     * @author: Amy
     * @create: 2023-02-19 20:58
     **/
    class LinkedList {
        
        static ListNode head;
    
    
        public static ListNode deleteNode(ListNode head){
        
            if(head==null|| head.next==null){
        
                return null;
            }
            ListNode second_last=head;//查找倒数第二个节点
            while(second_last.next.next!=null){
        
                second_last=second_last.next;
            }
            second_last.next=null;//更改倒数第二个的下一个也就是最后的null
    
            return head;//返回链表的新头
        }
        public static void push(int new_data) {
        
            ListNode new_node = new ListNode(new_data);
            new_node.next = head;
            head = new_node;
        }
        public void print(){
        
            ListNode node = head;
            while(node!=null){
        
                System.out.print(node.val+" ");
                node = node.next;
            }
    
        }
    
        public static void main (String[]args){
        
            LinkedList list = new LinkedList();
            list.push(1);
            list.push(3);
            list.push(8);
            list.push(4);
            System.out.println("\nCreated Linked list is:");
            list.print();
    
            deleteNode(head);
            System.out.println(
                    "\nLinked List after Deletion of position 3:");
            list.print();
    
        }
        static class ListNode {
        
            int val;
            ListNode next;
            ListNode(int value){
        
                val = value;
                next=null;
            }
        }
    }

Created Linked list is:
    4 8 3 1 
    Linked List after Deletion of position 3:
    4 8 3

# 2.其他删除的问题 #

## 1)指定位置删除元素Iterative Method to delete an element from the linked list: ##

### Steps: ###

1.  找到要删除的节点的前一个节点。
2.  更改前一个节点的下一个。
3.  要删除的节点的空闲内存。

### 代码 ###

class LinkedList {
        
        static ListNode head;
        public static ListNode deleteNode(ListNode head,int position){
        
            ListNode temp=head,pre=head;//创建一个指向链表头部的临时节点,创建指向链表头部的前一个节点
            for (int i = 0; i < position; i++) {
        //遍历链表找到给定位置的节点
                if(i==0&&position==1){
        //如果要删除的节点是头节点
                    head=head.next;
                }else{
        
                    if(i==position-1&& temp!=null){
        //如果找到要删除的节点
                        pre.next=temp.next;//设置前一个节点的下一个节点为当前节点的下一个节点
                    }else{
        
                        pre=temp;//将上一个节点移动到当前节点
                        if(pre==null){
        // 如果前一个节点为空，则位置大于列表中的节点数
                            break;
                        }
                        temp=temp.next;//将临时节点移动到下一个节点
                    }
                }
            }
            return head;//返回链表的新头
        }
        public static void push(int new_data) {
        
            ListNode new_node = new ListNode(new_data);
            new_node.next = head;
            head = new_node;
        }
        public void print(){
        
            ListNode node = head;
            while(node!=null){
        
                System.out.print(node.val+" ");
                node = node.next;
            }
    
        }
    
        public static void main (String[]args){
        
            LinkedList list = new LinkedList();
            list.push(1);
            list.push(3);
            list.push(8);
            list.push(4);
            System.out.println("\nCreated Linked list is:");
            list.print();
    
            deleteNode(head,3);
            System.out.println(
                    "\nLinked List after Deletion of position 3:");
            list.print();
    
        }
        static class ListNode {
        
            int val;
            ListNode next;
            ListNode(int value){
        
                val = value;
                next=null;
            }
        }
    
    }

Created Linked list is:
    4 8 3 1 
    Linked List after Deletion of position 3:
    4 8 1

## 2)根据值删除元素 Delete the first node in a linked list where data == key: ##

`Time Complexity`: `O(n)`  
`Auxiliary Space`: `O(1)`  
![在这里插入图片描述][75f0918328564dddbe67fe8c96d1cee9.png]

### 代码 ###

class LinkedList {
        
        static ListNode head;
        public void deleteNode(int data){
        
            ListNode temp=head,pre=null;
    
            if(temp!=null&&temp.val==data){
        // 如果头节点本身持有要删除的值
                head=temp.next;
                return;
            }
            // 搜索要删除的值，跟踪 
            // 前一个节点，因为我们需要更改 temp.next
            while(temp!=null&&temp.val!=data){
        
                pre=temp;
                temp=temp.next;
            }
            if(temp==null) return;  // 如果键不在链表中
            pre.next=temp.next;//取消节点与链表的链接
    
        }
        public static void push(int new_data) {
        
            ListNode new_node = new ListNode(new_data);
            new_node.next = head;
            head = new_node;
        }
        public void print(){
        
            ListNode node = head;
            while(node!=null){
        
                System.out.print(node.val+" ");
                node = node.next;
            }
    
        }
    
        public static void main (String[]args){
        
            LinkedList list = new LinkedList();
            list.push(1);
            list.push(3);
            list.push(8);
            list.push(4);
            System.out.println("\nCreated Linked list is:");
            list.print();
    
            list.deleteNode(8);
            System.out.println(
                    "\nLinked List after Deletion of 8:");
            list.print();
        }
        static class ListNode {
        
            int val;
            ListNode next;
            ListNode(int value){
        
                val = value;
                next=null;
            }
        }
    }

Created Linked list is:
    4 8 3 1 
    Linked List after Deletion of 8:
    4 3 1

## 3)递归方法从链表中删除节点Recursive Method to delete a node from linked list: ##

### 代码 ###

class LinkedList {
        
        static ListNode head;
        public static ListNode deleteNode(ListNode node,int k){
        
            if(k<1) return node;//如果无效 k
            if(node==null) return null;//如果链表为空
            if(k==1){
        //基本情况（开始需要删除）
                ListNode res = node.next;
                return res;
            }
            node.next=deleteNode(node.next,k-1);
            return node;
        }
        public static void push(int new_data) {
        
            ListNode new_node = new ListNode(new_data);
            new_node.next = head;
            head = new_node;
        }
        public void print(){
        
            ListNode node = head;
            while(node!=null){
        
                System.out.print(node.val+" ");
                node = node.next;
            }
        }
        public static void main (String[]args){
        
            LinkedList list = new LinkedList();
            list.push(1);
            list.push(3);
            list.push(8);
            list.push(4);
            System.out.println("\nCreated Linked list is:");
            list.print();
    
            deleteNode(head,3);
            System.out.println(
                    "\nLinked List after Deletion of position 3:");
            list.print();
    
        }
        static class ListNode {
        
            int val;
            ListNode next;
            ListNode(int value){
        
                val = value;
                next=null;
            }
        }
    
    }

Created Linked list is:
    4 8 3 1 
    Linked List after Deletion of position 3:
    4 8 1

[70ab2350756844a2a95b30cdcb391368.gif_pic_center]: https://img-blog.csdnimg.cn/img_convert/70ab2350756844a2a95b30cdcb391368.gif#pic_center
[75f0918328564dddbe67fe8c96d1cee9.png]: https://img-blog.csdnimg.cn/75f0918328564dddbe67fe8c96d1cee9.png