【题18 删除链表的节点】

Love The Way You Lie 2022-03-26 03:09 180阅读 0赞

**【题18 删除链表的节点】**  
**【题目一：在O（1）时间内删除链表节点】**  
给定单向链表的头指针和一个节点指针：定义一个函数在O（1）时间内删除该节点

**分析：**  
常规做法是从链表的头节点开始，顺序遍历查找要删除的节点。  
并在链表中删除该结点，想删除i，从a开始遍历。时间复杂度为**O（n）**  
![在这里插入图片描述][20190115115632773.png]

之所以需要从头开始查找，是因为我们需要得到将被删除的节点的前一个节点。在单向链表中，节点中没有指向前一个节点的指针，所以只好从链表的头节点开始顺序查找。  
**法二**  
如果把 下一个节点的内容复制到需要删除的节点上，覆盖原有的内容，再把下一个节点删除，就相当于把当前需要删除的节点删除了？  
如图c要删除i，先把i的下一个节点j的内容复制到i然后把i的指针指向节点j的下一个节点，此时，删除j刚好把节点i删除了  
![在这里插入图片描述][20190115115749453.png]

**问题：**  
如果要删除的节点位于链表尾部，没有下一个节点还要从头开始顺序遍历  
**注意：**  
如果链表中只有一个节点，又要删除链表的头节点（也是尾结点）  
此时在删除节点之后，还需把链表的头节点设为null

**分析时间复杂度：**

*  对于n-1个非尾节点，在O（1）时间把下一个节点的内存复制覆盖要删除的节点，并删除下一个节点。
 *  对于尾结点，需要顺序查找O(n)

总的平均时间复杂度是\[(n-1)\*O(1)+O(n)\]/n 结果O（1）

上述代码并不完美，因为它基于一个假设，要删除的节点的确在链表中，需要O（n）时间才能 判断链表中是否包含某一结点

受到O(1)时间限制，不得不把确保节点在链表中的责任推给函数调用者。  
**实现**

package ti18;
    
    public class Lian {
    	
    	//删除链表中节点
    	public static class ListNode{
    		private int data;
    		private ListNode next;
    		public ListNode(int data,ListNode next){
    			this.data = data;
    			this.next = next;
    		}
    	}
    	
    	public static void deleteNode(ListNode head,ListNode node){
    		//删除尾结点
    		if(node.next == null){
    			while(head.next != null){
    				head = head.next;
    			}
    			head.next = null;
    		}
    		//删除节点是头节点
    		else if(node == head){
    			head = null;
    		}
    		//删除的是中间的普通节点
    		else{
    			node.data = node.next.data;
    			node.next = node.next.next;
    		}
    	}
    	
    	public static void main(String[] args) {
    		ListNode tail = new ListNode(1,null);
    		ListNode c    = new ListNode(2,tail);
    		ListNode b    = new ListNode(3,c);
    		ListNode head = new ListNode(4,b);
    		deleteNode(head,c);
    		while(head != null){
    			System.out.println(head.data);
    			head = head.next;
    		}
    	}
    }

【题目二：删除链表中重复的节点】  
在一个排序的链表中，如何删除重复的节点？

（1） 确定删除函数的参数，输入待删除链表的头节点，头节点也可能被删掉  
（2） 从头遍历整个链表，为了保证删除后的链表仍然相连，  
（3） 要把当前节点的前一个节点和后面值比当前节点值大的节点相连，确保当前节点的前一个节点，始终与下一个没有重复的节点连接在一起。

**实现**

package ti18;
    
    public class Lian2 {
    	
    	public static class ListNode{
    		private int data;
    		private ListNode next;
    		public ListNode(int data,ListNode next){
    			this.data = data;
    			this.next = next;
    		}
    	}
    	
    	public static ListNode deleteDuplication(ListNode head){
    		if(head == null || head.next == null){
    			return head;
    		}
    		ListNode preNode = null;
    		ListNode pNode = head;
    		while(pNode != null){
    			ListNode pNext = pNode.next;
    			boolean needDelete = false;
    			if(pNext !=null && pNode.data == pNext.data){
    				needDelete = true;
    			}
    			if(!needDelete){
    				preNode = pNode;
    				pNode = pNode.next;
    			}
    			else{
    				int value = pNode.data;
    				ListNode toBeDelete = pNode;
    				while(toBeDelete != null && toBeDelete.data == value){
    					pNext = toBeDelete.next;
    					toBeDelete = pNext;
    				}
    				if(preNode == null){
    					head = pNext;
    				}
    				else
    					preNode.next = pNext;
    				pNode = pNext;
    			}
    		}
    		return head;
    	}
    	
    	public static void main(String[] args) {
    		ListNode tail = new ListNode(5,null);
    		ListNode c = new ListNode(4,tail);
    		ListNode b = new ListNode(4,c);
    		ListNode a = new ListNode(3,b);
    		ListNode e = new ListNode(3,a);
    		ListNode d = new ListNode(2,e);
    		ListNode head = new ListNode(1,d);
    		
    		deleteDuplication(head);
    		
    		while(head != null){
    			System.out.println(head.data+" ");
    			head = head.next;
    		}
    	}
    }
    
    //方法二：递归实现
    /*
     public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        public ListNode deleteDuplication(ListNode pHead)
        {
            if(pHead == null ||pHead.next == null) return pHead;
            if(pHead.val == pHead.next.val){
                ListNode pNode = pHead.next;
                while(pNode != null && pNode.val == pHead.val){
                    pNode = pNode.next;
                }
                return deleteDuplication(pNode);
            }else{
                pHead.next = deleteDuplication(pHead.next);
                return pHead;
            }
        }
    }

参考：  
1.《剑指offer》  
2.[https://blog.csdn.net/qfc8930858/article/details/83241509][https_blog.csdn.net_qfc8930858_article_details_83241509]

[20190115115632773.png]: /images/20220326/56eb6f7aa47b492e9b3bfa2551f8093e.png
[20190115115749453.png]: /images/20220326/76fcd44945624d03befd3873736475c9.png
[https_blog.csdn.net_qfc8930858_article_details_83241509]: https://blog.csdn.net/qfc8930858/article/details/83241509