在单链表中查找倒数第二个节点

Question

所以我有一个单链表的实现，我正在尝试添加一个方法来报告列表的倒数第二个节点。但是，我不确定是否允许我在 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++;        }

Answer 1

删除字段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;

}

Answer 2

为什么不跟踪倒数第二个节点？

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

    }

}