剑指Offer Java版 面试题18：删除链表的节点

题目一：在O(1)时间内删除链表节点。
给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。

参考答案

class ListNode {
    int value;
    ListNode next;
}

public void deleteNode(ListNode head, ListNode toBeDeleted) {
    if (head == null || toBeDeleted == null) {
        return;
    }
    if (toBeDeleted.next != null) {
        // 要删除的节点不是尾节点
        ListNode pNext = toBeDeleted.next;
        toBeDeleted.value = pNext.value;
        toBeDeleted.next = pNext.next;
        pNext = null;
    } else if (head == toBeDeleted) {
        // 链表只有一个节点，删除头节点（也是尾节点）
        head = null;
        toBeDeleted = null;
    } else {
        // 链表中有多个节点，删除尾节点
        ListNode node = head;
        while (node.next.next != null) {
            node = node.next;
        }
        node.next = null;
        toBeDeleted = null;
    }
}

复杂度分析

• 时间复杂度：O(1)。
• 空间复杂度：O(1)。

题目二：删除链表中重复的节点。
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

练习地址

https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef

参考答案

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode pre = null, node = pHead;
        while (node != null) {
            boolean needDelete = false;
            if (node.next != null && node.next.val == node.val) {
                needDelete = true;
            }
            if (needDelete) {
                int value = node.val;
                while (node != null && node.val == value) {
                    node = node.next;
                }
                if (pre == null) {
                    pHead = node;
                } else {
                    pre.next = node;
                }
            } else {
                pre = node;
                node = node.next;
            }
        }
        return pHead;
    }
}

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题