Java >> Tutoriel Java >  >> Java

Programme pour trouver le nième nœud à partir de la fin d'une liste chaînée

Question  :étant donné une liste chaînée et un nombre n, écrivez un programme qui trouve la valeur au nième nœud à partir de la fin de la liste chaînée.

Méthode 1 - Utiliser la longueur de la liste liée

1. Calculez la longueur de la liste liée. Suivez ce tutoriel Trouver la longueur d'une donnée de liste chaînée

2. Imprimez le (len – n + 1)ème nœud à partir du début de la liste chaînée.

for (int i = 1; i < length - nthNode + 1; i++)

Coder en Java

package in.eyehunt.data.struc;
public class LinkedList {

    Node head; // head of list
    // Linked list Node.
    class Node {
        int data;
        Node next;
        // Parameterized constructor
        Node(int d) {
            data = d;
            next = null;
        }
    }
    void push(int n) {
        //create new node
        Node newNode = new Node(n);
        // next node is head
        newNode.next = head;
        // move had point to new node
        head = newNode;
    }
    void findNthNode(int nthNode) {
        Node findNode = head;
        int length = count();
        if (head == null) {
            System.out.println("LinkedList is null");
        } else if (nthNode > length) {
            System.out.println("\nFinding nth node not existing in List");
        } else {
            for (int i = 1; i < length - nthNode + 1; i++)
                findNode = findNode.next;
            System.out.println("\nnth node in list from end is " + findNode.data);
        }
    }
    //Returns count of nodes in linked list (iteration)
    public int count() {
        int a = 0;
        Node n = head;
        while (n != null) {
            n = n.next;
            a++;
        }
        return a;
    }
    void printAllNodes() {
        Node node = head;
        System.out.print("Given Linked list : ");
        while (node != null) {
            System.out.print("-> " + node.data);
            node = node.next;
        }
    }
    public static void main(String a[]) {
        //create a simple linked list with 4 nodes
        LinkedList linkedList = new LinkedList();
        linkedList.push(1);
        linkedList.push(9);
        linkedList.push(7);
        linkedList.push(2);
        linkedList.push(4);
        linkedList.printAllNodes();
        linkedList.findNthNode(9);
    }
}

Sortie :

Liste chaînée donnée :-> 4-> 2-> 7-> 9-> 1
Le nième nœud de la liste à partir de la fin est 9

Complexité temporelle : O(n) where n is the length of linked list.

Voici d'autres questions d'entretien LinkedList :

  1. Inverser une structure de données de liste chaînée en Java
  2. Trouvez le milieu d'une structure de données de liste chaînée donnée
  3. Insérer un nouveau nœud dans une structure de données de liste chaînée
  4. Trouver la longueur d'une structure de données de liste chaînée (itérative et récursive)

Balise Java