6

JZ-069-在 O(1) 时间内删除链表节点

 3 years ago
source link: https://segmentfault.com/a/1190000041450918
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

JZ-069-在 O(1) 时间内删除链表节点

发布于 2 月 23 日

在 O(1) 时间内删除链表节点

在 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) {
    
    }
}

【每日寄语】 窦燕山，有义方；教五子，名俱扬。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK