codebytes: An algorithm to delete a node in the middle of a singly linked list, given only access to that node.
Q. Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
EXAMPLE
Input: the node c from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e
public static boolean deleteNode(LinkedListNode n) {
if (n == null || n.next == null) {
return false; // Failure
}
LinkedListNode next = n.next;
n.data = next.data;
n.next = next.next;
return true;
}
Q. Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
EXAMPLE
Input: the node c from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e
private static void deleteMiddleNode(LinkedList.Node node){ if(node.next == null)return; //End node provided LinkedList.Node prev = node; node = node.next; while(node.next!=null){ prev.value = node.value; prev = node; node = node.next; } prev.value = node.value; prev.next = null; }https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2002.%20Linked%20Lists/Q2_03_Delete_Middle_Node/Question.java
public static boolean deleteNode(LinkedListNode n) {
if (n == null || n.next == null) {
return false; // Failure
}
LinkedListNode next = n.next;
n.data = next.data;
n.next = next.next;
return true;
}
Note that this problem cannot be solved if the node to be deleted is the last node in the linked list. That's okay-your interviewer wants you to point that out, and to discuss how to handle this case. You could, for example, consider marking the node as dummy.
Read full article from codebytes: An algorithm to delete a node in the middle of a singly linked list, given only access to that node.