【剑指offer-Java版】13O(1)时间删除链表结点

我会带着你远行 2022-08-21 08:57 9阅读 0赞

O(1)时间删除链表结点  
前提是调用者知道要删除的结点的指针，而不是要删除结点的值  
不过此类删除问题，当然是存在各种边界条件了：  
1) 链表中只有一个结点 - 删除唯一的一个  
2) 要删除的结点是最后一个结点 -  
3) 要删除的结点不存在 - 多虑了，毕竟给定的参数是一个结点参数,所以不会存在这种问题，除非调用者故意给定

public class _Q13 {
    
        public void DeleteNode(ListNode head, ListNode toBeDeleted){
            if(head == null || toBeDeleted == null) return;
    
            if(toBeDeleted.next != null){ // 删除的结点不是尾结点-那么链表中至少有两个结点
                toBeDeleted.value = toBeDeleted.next.value;
                toBeDeleted.next = toBeDeleted.next.next;
                // 不知这种去掉引用的结点是否会被GC搜集掉 - 栈中是不会被GC的，因为存在过期对象的引用。但是链表引用直接去掉了
            }else{
                if(head.next == toBeDeleted){ // 删除唯一的一个结点
                    head.next = null;
                }else{ // 删除多个结点中的尾结点
                    ListNode node = head.next;
                    while((node.next != toBeDeleted) && (node.next != null)) node = node.next;
                    node.next = null;
                }
            }
        }
        }

测试代码：

public class _Q13Test extends TestCase {
        
    
        _Q13 deleteNode = new _Q13();
    
        public void test(){
            ListNode head = new ListNode();
    
            ListNode node1 = new ListNode();
            ListNode node2 = new ListNode();
            ListNode node3 = new ListNode();
            ListNode node4 = new ListNode();
    
            node1.value = 1;
            node2.value = 2;
            node3.value = 3;
            node4.value = 4;
    
            head.next = node1;
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = null;
    
            ListNode toBeDeleted1 = node1;
            ListNode toBeDeleted2 = node2;
            ListNode toBeDeleted3 = node3;
            ListNode toBeDeleted4 = node4;
    
            CommonUtils.PrintList(head);
            deleteNode.DeleteNode(head, toBeDeleted1);
            CommonUtils.PrintList(head);
        }
        }