创建方法 Insert Before Linked List

Question

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

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;
    }
}

创建方法 Insert Before Linked List

Create Method Insert Before Linked List

java

linked-list

insert

singly-linked-list