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

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->nullpublic Node<Integer> penultimate(Node<Integer> head) {&nbsp; &nbsp; Node<Integer> penultimate = null;&nbsp; &nbsp; Node<Integer> current = head;&nbsp; &nbsp; while (current != null) {&nbsp; &nbsp; &nbsp; &nbsp; if (current.getNext() == null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; penultimate = current;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; current = current.getNext();&nbsp; &nbsp; }&nbsp; &nbsp; return penultimate;}或者第三个（第二个？）到最后一个节点：// head: ...#->#->#->P->#->nullpublic Node<Integer> penultimate(Node<Integer> head) {&nbsp; &nbsp; Node<Integer> penultimate = null;&nbsp; &nbsp; Node<Integer> current = head;&nbsp; &nbsp; while (current != null) {&nbsp; &nbsp; &nbsp; &nbsp; if (current.getNext() == null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; penultimate = current;&nbsp; &nbsp; &nbsp; &nbsp; current = current.getNext();&nbsp; &nbsp; }&nbsp; &nbsp; 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() {&nbsp; &nbsp; return size;}public boolean isEmpty() {&nbsp; &nbsp; return size == 0;}public Integer first() {&nbsp; &nbsp; if (isEmpty()) {&nbsp; &nbsp; &nbsp; &nbsp; return null;&nbsp; &nbsp; }&nbsp; &nbsp; return head.getElement();}public Integer last() {&nbsp; &nbsp; if(isEmpty()) {&nbsp; &nbsp; &nbsp; &nbsp; return null;&nbsp; &nbsp; }&nbsp; &nbsp; return tail.getElement();}public void addFirst(Integer i) {&nbsp; &nbsp; if (size == 1) {&nbsp; &nbsp; &nbsp; &nbsp; secondToLast = head;&nbsp; &nbsp; }&nbsp; &nbsp; head = new Node<> (i, head);&nbsp; &nbsp; if(size == 0) {&nbsp; &nbsp; &nbsp; &nbsp; tail = head;&nbsp; &nbsp; }&nbsp; &nbsp; size++;}public void addLast(Integer i) {&nbsp; &nbsp; Node<Integer> newest = new Node<>(i,null);&nbsp; &nbsp; if(isEmpty()) {&nbsp; &nbsp; &nbsp; &nbsp; head = newest;&nbsp; &nbsp; }&nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; tail.setNext(newest);&nbsp; &nbsp; &nbsp; &nbsp; secondToLast = tail;&nbsp; &nbsp; }&nbsp; &nbsp; tail = newest;&nbsp; &nbsp; size++;}public Integer removeFirst() {&nbsp; &nbsp; if(isEmpty()) {&nbsp; &nbsp; &nbsp; &nbsp; return null;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; Integer answer = head.getElement();&nbsp; &nbsp; head = head.getNext();&nbsp; &nbsp; size--;&nbsp; &nbsp; if(size == 0) {&nbsp; &nbsp; &nbsp; &nbsp; tail = null;&nbsp; &nbsp; }&nbsp; &nbsp; if (size == 1) {&nbsp; &nbsp; &nbsp; &nbsp; secondToLast = null;&nbsp; &nbsp; }&nbsp; &nbsp; return answer;}public void getPenultimate() {&nbsp; &nbsp; if(isEmpty()) {&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("List is empty. Please check.");&nbsp; &nbsp; }&nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("The second last node is: " + secondToLast);&nbsp; &nbsp; }}