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:
- Reversere en linket listedatastruktur i java
- Find midten af en given linket listedatastruktur
- Indsættelse af en ny node i en linket listedatastruktur
- Find længden af en linket listedatastruktur (Iterativ og rekursiv)