所以我有一個單鏈表的實現，我正在嘗試添加一個方法來報告列表的倒數第二個節點。但是，我不確定是否允許我在 Node 類下編寫該方法，然后從單鏈表類訪問它。如果我這樣做，我的節點類的實例變量（'head' 用作訪問倒數第二個方法的變量，但也用作倒數第二個方法的輸入?？梢詥?？下面是我的實現/嘗試。public class SinglyLinkedList { private static class Node<Integer>{ private Integer element; private Node<Integer> next; private Node<Integer> penultimate; public Node(Integer e, Node<Integer> n) { element = e; next = n; penultimate = null; } public Integer getElement() {return element;} public Node<Integer> getNext(){return next;} public void setNext(Node<Integer> n) {next = n;} public Node<Integer> penultimate(Node<Integer> head) { Node<Integer> current = head; while(current != null) { if(head.getNext() == null) { penultimate = head; } else { current = current.getNext(); } } return penultimate; } } private Node<Integer> head = null; private Node<Integer> tail = null; private int size = 0; public SinglyLinkedList() {} public int size() { return size; } public boolean isEmpty() { return size == 0; } public Integer first() { if (isEmpty()) { return null; } return head.getElement(); } public Integer last() { if(isEmpty()) { return null; } return tail.getElement(); } public void addFirst(Integer i) { head = new Node<> (i, head); if(size == 0) { tail = head; } size++; }
2 回答
千萬里不及你
TA貢獻1784條經驗 獲得超9個贊
刪除字段penultimate。你不希望它在每個節點中，實際上在沒有節點，而是計算出來的。
在 Node 的倒數第二個方法head中不應該在循環中使用。
//private Node<Integer> penultimate;
// head: ...#->#->#->P->null
public Node<Integer> penultimate(Node<Integer> head) {
Node<Integer> penultimate = null;
Node<Integer> current = head;
while (current != null) {
if (current.getNext() == null) {
penultimate = current;
break;
}
current = current.getNext();
}
return penultimate;
}
或者第三個（第二個？）到最后一個節點：
// head: ...#->#->#->P->#->null
public Node<Integer> penultimate(Node<Integer> head) {
Node<Integer> penultimate = null;
Node<Integer> current = head;
while (current != null) {
if (current.getNext() == null) {
break;
}
penultimate = current;
current = current.getNext();
}
return penultimate;
}
絕地無雙
TA貢獻1946條經驗 獲得超4個贊
為什么不跟蹤倒數第二個節點？
private Node<Integer> head = null;
private Node<Integer> tail = null;
private Node<Integer> secondToLast = null;
private int size = 0;
public SinglyLinkedList() {}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public Integer first() {
if (isEmpty()) {
return null;
}
return head.getElement();
}
public Integer last() {
if(isEmpty()) {
return null;
}
return tail.getElement();
}
public void addFirst(Integer i) {
if (size == 1) {
secondToLast = head;
}
head = new Node<> (i, head);
if(size == 0) {
tail = head;
}
size++;
}
public void addLast(Integer i) {
Node<Integer> newest = new Node<>(i,null);
if(isEmpty()) {
head = newest;
}
else {
tail.setNext(newest);
secondToLast = tail;
}
tail = newest;
size++;
}
public Integer removeFirst() {
if(isEmpty()) {
return null;
}
Integer answer = head.getElement();
head = head.getNext();
size--;
if(size == 0) {
tail = null;
}
if (size == 1) {
secondToLast = null;
}
return answer;
}
public void getPenultimate() {
if(isEmpty()) {
System.out.println("List is empty. Please check.");
}
else {
System.out.println("The second last node is: " + secondToLast);
}
}
添加回答
舉報
0/150
提交
取消