当您仅被授予对节点的访问权限时，如何删除链接列表中的节点

My understanding is that in order to delete a node in singly linked list, we need access to the current node and previous node. I have the following logic for it:

我的理解是,为了删除单链表中的节点,我们需要访问当前节点和前一节点。我有以下逻辑:

public SingleNode delete(int val) {

    SingleNode current = head;
    SingleNode prev = head;

    while(current.data != val) {

        if (current.next == null) {
            return null;
        } else {
            prev = current;
            current = current.next;
        }

    }

    if(current == head) {
        head = current.next;
    } else {
        prev.next = current.next;
    }

    return current;

}

How can I change the code so that I can delete a node in linked list when you are given access to only the current node?

如何更改代码,以便在您只能访问当前节点时可以删除链表中的节点?

4 个解决方案

#1

How can I change the code so that I can delete a node in linked list when you are given access to only the current node?

如何更改代码,以便在您只能访问当前节点时可以删除链表中的节点?

For a singly-linked list, you cannot remove a node with a given reference unless you have either the previous node, or you can access the head of the list.

对于单链接列表,除非您具有上一个节点,否则无法删除具有给定引用的节点,或者您可以访问列表的头部。

If you have the head, you can find the previous node ... in O(N) steps.

如果您有头,您可以在O(N)步骤中找到上一个节点....

There is a way to remove a node by modifying it that works in most cases, but there are various edge cases that make it difficult. (And it certainly won't work if you need to support concurrent removal and iteration, etcetera.)

有一种方法可以通过修改节点来删除节点,这种节点在大多数情况下都有效,但是有各种边缘情况会使其变得困难。 (如果你需要支持并发删除和迭代,它当然不会起作用,等等。)

#2

If only the access to the node to be deleted you could do below, by setting the data and next pointers of next node to current node.

如果只能访问要删除的节点,则可以通过将下一个节点的数据和下一个指针设置为当前节点来实现。

public void delete (Node<E> node){
    if (node.next! = null){
        node.data = node.next.data;
        node.next = node.next.next;
    }else{
        node.next = null;
        node.data = null;
    }

}

If the data structure defined with sentinel then we don't need the null check, simply change the pointers of data and next pointers of current to next

如果用sentinel定义的数据结构然后我们不需要空检查,只需更改数据的指针和下一个当前指针到下一个

*Sent from mobile, may contain typo

*从手机发送,可能包含拼写错误

UPDATE

Here is the partial implementation with sentinel

以下是Sentinel的部分实现

public class LinkedList<E> {

    private static class Node<E> {
        E element;
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node [element=" + element + ", next=" + next + "]";
        }

    }

    private int size;
    private Node<E> head; // sentinel
    private Node<E> tail; // sentinel

    public LinkedList() {
        tail = new Node<>(null, null);
        head = new Node<>(null, tail);
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public Node<E> head() {
        return head.next;
    }

    public Node<E> tail() {
        // TODO
    }

    public void addFirst(E e) {
        addBetween(head, e, head.next);
    }

    public void addLast(E e) {
        // TODO
    }

    public void addBetween(Node<E> prev, E element, Node<E> next) {
        Node<E> curr = new Node<>(element, next);
        prev.next = curr;
        size++;
    }

    public Node<E> node(E e) {
        Node<E> temp = head;
        while (temp != null) {
            if (temp.element == e) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }

    public E delete(Node<E> node) {
        E e = node.element;
        node.element = node.next.element;
        node.next = node.next.next;
        return e;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node<E> temp = head;
        while (temp != null) {
            sb.append(temp.element + " ");
            temp = temp.next;
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        LinkedList<Integer> ll = new LinkedList<>();
        ll.addFirst(10);
        ll.addFirst(20);
        ll.addFirst(30);
        ll.addFirst(40);
        ll.addFirst(50);
        System.out.println("Linked List :: " + ll);
        Node<Integer> node = ll.node(10);
        System.out.println("Node :: " + node);
        System.out.println("Element :: " + ll.delete(node));
        System.out.println("Final List :: " + ll);
    }
}

output

Linked List :: null 50 40 30 20 10 null 
Node :: Node [element=10, next=Node [element=null, next=null]]
Element :: 10
Final List :: null 50 40 30 20 null 

#3

struct node *temp  = node_ptr->next;
node_ptr->data  = temp->data;
node_ptr->next  = temp->next;
free(temp);

#4

void deleteNode (struct node *node_ptr)

void deleteNode(struct node * node_ptr)

{

struct node *temp = node_ptr->next;

struct node * temp = node_ptr-> next;

node_ptr->data = temp->data;

node_ptr-> data = temp-> data;

node_ptr->next = temp->next;

node_ptr-> next = temp-> next;

free(temp);

}

The above function delete the node with a single pointer. The method doesn’t work if the node to be deleted is the last node of the list.

上面的函数用一个指针删除节点。如果要删除的节点是列表的最后一个节点,则该方法不起作用。