Java >> Java tutorial >  >> Java

Program til at finde n'te node fra slutningen af ​​en linket liste

Spørgsmål :Givet en sammenkædet liste og et tal n, skriv et program, der finder værdien ved den n'te node fra slutningen af ​​den sammenkædede liste.

Metode 1 – Brug længden af ​​linket liste

1. Beregn længden af ​​Linked List. Følg denne vejledning Find længden af ​​en linket listedata

2. Udskriv den (len – n + 1) node fra begyndelsen af ​​den linkede liste.

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

Kode i 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);
    }
}

Output:

Givet linket liste:-> 4-> 2-> 7-> 9-> 1
n. node i listen fra ende er 9

Tidskompleksitet: O(n) where n is the length of linked list.

Her er flere LinkedList-interviewspørgsmål:

  1. Reversere en linket listedatastruktur i java
  2. Find midten af ​​en given linket listedatastruktur
  3. Indsættelse af en ny node i en linket listedatastruktur
  4. Find længden af ​​en linket listedatastruktur (Iterativ og rekursiv)

Java tag