public Object removeElementBefore(Object o) {
if (o == null)
return null;
Node prev = head;
Node crt = prev == null ? null : prev.next;
if (crt == null)
return null;
// trying to find the element right before the parameter
while(crt.next != null && !o.equals(crt.next.content)) {
prev = prev.next;
crt = crt.next;
}
if (crt.next == null)
return null;
// remove crt node from list
prev.next = crt.next;
crt.next = null;
// return the removed content
return crt.content;
}
Removing an element before the object passed in as the parameter in a Singly Linked List
-
23-06-2023 - |
質問
I'm trying to write a method for to remove an element before the object passed in as a parameter in a Singly Linked List.
So far I have this, but honestly I'm completely lost.
public void removeElementBefore(Object o) {
Node n = new Node(o);
Node crt = head;
// trying to find the element right before the parameter
while(crt.next != n)
crt = crt.next;
// getting the new content
n = crt.next.content;
return n;
}
}
More of the program for context: method to remove last element in the list
public Object removeLast() throws EmptyListException {
if (head == null) throw new EmptyListException();
Object o;
// If there is only one element, we need to modify the head of the list
if (head.next == null) {
o = head.content;
head.content = null;
head = null;
return o;
}
// We need to go to the second-to-last element
Node crt = head;
while (crt.next.next != null)
crt = crt.next;
// Now get the content
o = crt.next.content;
// Remove all references that are not needed
crt.next.content = null;
crt.next = null;
// And we're done
return o;
}
解決
他のヒント
Here's a non-Java specific algorithm (not necessarily completely compact). You should be able to translate it into Java code.
Given linked list L and item to remove item.
cur = L.head
if (cur == item)
L.head = cur.next
return
prev = cur
cur = cur.next
while (cur != item):
if NOT (cur.next exists):
// cur is the end of the list, so the item doesn't exist in this list
return
prev = cur
cur = cur.next
// If you reach this point, the desired item has been found, and prev
// precedes it in the list
prev.next = cur.next
public void removeElementBefore(Node before) {
if (before == null) return;
Node n = head;
if (n.next == before) {
head = n.next;
return;
}
while (n.next.next != before) {
if (n.next.next == null) return;
n = n.next;
}
n.next = n.next.next;
}
所属していません StackOverflow