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

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++;
        }
        public void addLast(Integer i) {
            Node<Integer> newest = new Node<>(i,null);
            if(isEmpty()) {
                head = newest;
            }
            else {
                tail.setNext(newest);
            tail = newest;
            size++;
            }
        }
        public Integer removeFirst() {
            if(isEmpty()) {
                return null;
                }
            Integer answer = head.getElement();
            head = head.getNext();
            size--;
            if(size == 0) {
                tail = 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: " + head.penultimate(head));
            }

        }

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