关于java:JZ069在-O1-时间内删除链表节点

44次阅读

共计 791 个字符，预计需要花费 2 分钟才能阅读完成。

在 O(1) 工夫内删除链表节点。

计划： 如果该节点不是尾节点，那么能够间接将下一个节点的值赋给该节点，而后令该节点指向下下个节点，再删除下一个节点，工夫复杂度为 O(1)。否则，就须要先遍历链表，找到节点的前一个节点，而后让前一个节点指向 null，工夫复杂度为 O(N)。

题目链接 : [在 O(1) 工夫内删除链表节点 ]()

/**
 * 在 O(1) 工夫内删除链表节点
 */
public class Jz69 {

    /**
     * 计划：* 如果该节点不是尾节点，那么能够间接将下一个节点的值赋给该节点，而后令该节点指向下下个节点，再删除下一个节点，工夫复杂度为 O(1)。* 否则，就须要先遍历链表，找到节点的前一个节点，而后让前一个节点指向 null，工夫复杂度为 O(N)。*
     * @param head
     * @param tobeDelete
     * @return
     */
    public ListNode deleteNode(ListNode head, ListNode tobeDelete) {if (head == null || tobeDelete == null) {return null;}
        if (tobeDelete.next != null) {
            // 要删除的节点不是尾结点
            ListNode next = tobeDelete.next;
            tobeDelete.val = next.val;
            tobeDelete.next = next.next;
        } else {if (head == tobeDelete) {
                // 只有一个节点
                head = null;
            } else {
                ListNode cur = head;
                while (cur.next != tobeDelete) {cur = cur.next;}
                cur.next = null;
            }
        }

        return head;
    }

    public static void main(String[] args) {}}