链表Delete和insertAfter方法

Question

我在delete和insertAfter方法方面遇到了问题。方法是执行操作，如果操作成功(true(或不成功(false(，则返回布尔值。InsertAfter方法将插入一个字符串，但始终在同一位置，Delete方法将始终删除同一节点。

private class StrNode {
String data;
StrNode next;
}
private StrNode head;   // the head of the singly-linked list.
public StringList() {
head = null;
}
public void prepend(String s) {                                                         
var newNode = new StrNode();
// TODO: Adds an item to the start of the list.     
newNode.data = s;
if(head == null) {
head = newNode;
}
else {
newNode.next = head;
head = newNode;
}

}
/**
* Inserts an item after the first instance of a key if the key exists.
*
* @param s the item to insert
* @param key the item in the list to insert after
* @return whether the insertion was successful
*/
public boolean insertAfter(String s, String key) {                                                      
// TODO:    Inserts an item after the first instance of a key if the key exists.
var newNode = new StrNode();
StrNode current = head;
newNode.data = s;

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


return false;
}

/**
* Deletes the first instance of an item from the list.
*
* @param key the value of the item to delete from the list.
* @return whether the deletion was successful.
*/
public boolean delete(String key) {                                                     
// TODO:    Deletes the first instance of an item from the list.
StrNode current = head;
StrNode sucNode = current;

if(current == null) {
sucNode = head.next;
head = sucNode;
return true;
}
else if(current.next != null) {
sucNode = current.next.next;
current.next = sucNode;
return true;
}
return false;
}

我想在三个之后插入四个的主要方法应该是：三，二，四，一。但我得到：三，四，二，一

delete方法只删除了四个实际上应该是这样的：三、四、二但我得到：三，二，一main：

public static void main(String[] args) {

StringList s = new StringList();

s.prepend("one");
s.prepend("two");
s.prepend("three");
System.out.println(s);

s.insertAfter("four", "three");
System.out.println(s);

System.out.println(s.delete("one"));
System.out.println(s);


}

Answer 1

您询问了两种方法：

insertAfter

一些问题：

• 您不使用参数key
• 在head为null的情况下，您永远无法满足节点应插入在带有键的节点之后的条件，因此在这种情况下，应返回false
• current初始化为head，因此您将新节点分配给head.next，而不检查key匹配
• 您总是返回false，从不返回true

您应该通过迭代列表来查找给定的密钥：

public boolean insertAfter(String s, String key) {
// Inserts an item after the first instance of a key if the key exists.
StrNode current = head;

while (current != null) {
if (current.data == key) { // found the insertion spot
var newNode = new StrNode();
newNode.data = s;
newNode.next = current.next;
current.next = newNode;
return true;
}
current = current.next; // need to walk along the list
}
return false; // didn't find the key
}

delete

• 您不使用参数key
• 如果head(即current(为null，则永远无法满足要删除的节点应具有给定密钥的条件，因此在这种情况下，应返回false
• 在另一种情况下，您总是在不检查key匹配的情况下删除第二个节点

已更正：

public boolean delete(String key) {                                                     
// Deletes the first instance of an item from the list.
StrNode current = head;
if (head == null) return false;
if (head.data == key) {
head = head.next;
return true;
}
while (current.next != null) {
if (current.next.data == key) { // found it
current.next = current.next.next; // delete it
return true;
}
current = current.next; // need to walk along the list
}
return false; // not found
}

关于prepend的备注：

您不需要if语句。当head为空时，else块中的代码工作正常，因此您的代码可以是：

public void prepend(String s) { 
// Adds an item to the start of the list. 
StrNode node = new StrNode();
node.data = s;
node.next = head;
head = node;
}