创建方法在链表之前插入

Question

我已经创建了一个insert-after方法，现在我必须通过修改我的方法来创建一个insert before方法。我需要更改什么才能成为insert-bfore方法？

public void insertAfter(int key, int input){
Node ndInput = new Node(input, null);
Node temp = head;
do{
if(temp.data == key){
ndInput.next = temp.next;
temp.next = ndInput;
if(ndInput.next == null) tail = ndInput;
break;
}
temp = temp.next;
}while(temp != null);
}

Answer 1

首先，当列表为空时，当前代码将失败。此外，最好是：

• 只有在找到密钥时才创建节点
• 使用Node构造函数的第二个参数立即初始化next属性

所以：

public void insertAfter(int key, int input) {
Node temp = head;
while (temp != null) { // Loop condition should be here, to deal with empty list
if (temp.data == key) {
temp.next = new Node(input, temp.next); // Create here & use 2nd arg
if (temp == tail) tail = temp.next;
break;
}
temp = temp.next;
}
}

要制作insertBefore，请在temp.next中查找密钥，而不是在temp中查找密钥。由于您仍然需要处理空列表的情况，因此这可以更好地成为一个单独的条件。

当插入的节点成为第一个节点时，还需要调整头部。另一方面，不再需要检查插入的节点是否成为尾部，因为这当然是不可能的：

public void insertBefore(int key, int input){
if (head == null) return; // Add as separate check
if (head.data == key) { // Case where head needs to refer to new node
head = new Node(input, head);
return;
}
Node temp = head;
while (temp.next != null) { // Check whether there is a next node
if (temp.next.data == key) { // Check data in next node
temp.next = new Node(input, temp.next);
break;
}
temp = temp.next;
}
}