Как удалить узел в конце связанного списка, не полагаясь на методы?

Question

У меня есть задание для моего класса кодирования, который просит меня создать связанный список, не полагаясь на класс SingleLinkedList или любой из его методов. Я застрял на последнем шаге, который просит меня удалить узел в конце связанного списка только с заголовком и хвостом, и я полагаю, что я не должен использовать метод removeLast.

Я знаю, что я должен использовать обход списка с циклом while, чтобы идентифицировать элемент перед последним элементом, но я не уверен, как это сделать. Вот все, что мой код до сих пор:

public class ListByHand { 

private static class Node<E> { 
    private E data; 
    private Node<E> next; 
    private E z; 

    private Node(E dataItem) { 
     data = z; 
     next = null; 
    } 

    private Node(E dataItem, Node<E> nodeRef) { 
     data = dataItem; 
     next = nodeRef; 
    } 
} 


public static void main(String[] args) { 

    // 1. Created original list containing Bob, Floyd, Mary, and Sue 
    Node<String> head = new Node<String>("Bob", null); 
    Node<String> nodeRef = head; 
    Node<String> tail = head; 
    tail.next = new Node<String>("Floyd", null); 
    tail = tail.next; 
    tail.next = new Node<String>("Mary", null); 
    tail = tail.next; 
    tail.next = new Node<String>("Sue", null); 
    tail = tail.next; 

    // Loop to print each name in the node 
    while(nodeRef != null) { 
     System.out.println(nodeRef.data); 
     nodeRef = nodeRef.next; 
    } 

    // 2. Added Mark to the front of the list 
    head = new Node<String>("Mark", head); 
    System.out.println(head.data); 

    // 3. Deleted the first node in the list 
    head = head.next; 
    System.out.println(head.data); 

    // 4. Added Peter to the end of the list 
    tail.next = new Node<String>("Peter", null); 
    tail = tail.next; 
    System.out.println(tail.data); 

    // 5. Deleted the last node in the list 

} 
} 

Answer 1

nodeRef = head; 
while (nodeRef.next != tail) nodeRef = nodeRef.next; 
nodeRef.next = null; 
tail = nodeRef; 

Answer 2

Как об этом.

Node<String> node = head; 
while (node.next != null && node.next.next != null) { 
    node = node.next; 
} 

Когда петля выходит, вы должны иметь от второго до последнего узла, правильно?

Answer 3

Для начала, если вы можете, вы должны также включить в свой класс предыдущий узел. Оттуда вы можете легко взять хвост связанного списка и его предыдущего элемента. Если вы не можете, см. Вторую часть моего ответа.

Вы устанавливаете новый хвост в предыдущий элемент текущего хвоста и удаляете текущий хвост, и здесь вы идете.

tail = tail->previous; 
tail->next = null ; 

Однако я бы настоятельно советовал создавать методы для добавления и удаления.

Если вы не можете использовать список с двойной связью (без предыдущего элемента), вам нужно перебирать узлы по очереди, пока не достигнете последнего (хвост). Оттуда вы можете легко сделать то, что я предложил выше Однако я не вижу смысла иметь ваш последний элемент (из списка) в качестве переменной, так как вы не можете вернуться назад оттуда. Но если это ваше назначение в любом случае, это выглядит так:

Node<String> tmp = head ; 
while(tmp->next !=tail){ 
    tmp= tmp->next; 
} 
tail = tmp ; 
tail->next = null ;