如何在链表中的最后一个节点之前插入一个节点

Question

我在创建一个在java中最后一个元素之前添加项的方法时遇到了问题。我已经有了添加链表中最后一个元素的代码。

我应该如何实现addBeforeLast？

public class LinkedList {
Node first;
int size = 0;
public void addLast(int item) {
// If the list is empty, just create a node and make it
// the first.
if(first == null) {
first = new Node(item, null);
} else {
// Otherwise, find the last node
Node current = first;
// Stop when current's next is null: that's how
// we know it's the last element.
while(current.next != null) {
current = current.next;
}
Node prev = current;
// At this point, current is the last node.
// Make it point to a new node that will contain
// the given item.
current.next = new Node(item, prev);
}
size++;
}
}

Answer 1

试试这样的方法：

public void addBeforeLast(int a) {
if (first == null) throw new IllegalStateException("There is no last node"); // we cannot addBeforeLast when there is no last;
if (first.next == null) { // when only single node, we have to update first;
first = new Node(a, first);
return;
}
Node p = first;
while (p.next.next != null) p = p.next; // p.next will be the last node now;
p.next = new Node(a, p.next);
}

节点将有一个构造函数：

public Node(int theVal, Node theNext) {
this.val = theVal;
this.next = theNext;
}

顺便说一句，如果您坚持添加新节点，即使addBeforeLast没有节点。你可以使用这种方法：

public void addBeforeLast(int a) {
if (first == null || first.next == null) { // we have to update first;
first = new Node(a, first);
return;
}
Node p = first;
while (p.next.next != null) p = p.next; // p.next will be the last node now;
p.next = new Node(a, p.next);
}