Write a program to find the nth node from the beginning of the linked list.
Example 1:
Input: 5->2->8->4->1->NULL ,n=3
Output: Nth node is 8 //return 8
Example 2:
Input: 5->2->8->4->1->NULL ,n=10
Output: Nth node is not present //return -1
Approach:
Java
public class LinkListSearchNthElement {public static void main(String[] args) {ListNode l = new ListNode(5);l.next = new ListNode(2);l.next.next = new ListNode(8);l.next.next.next = new ListNode(4);l.next.next.next.next = new ListNode(1);int value = 3;int nth = searchGivenNode(l, value);System.out.println("Nth node is " + nth);}private static int searchGivenNode(ListNode head, int value) {int nth = 0;while (head != null) {nth++;if (nth == value) {return head.val;}head = head.next;}return -1;}}class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}}// Time Complexity : O(n)
C++
#include <bits/stdc++.h>using namespace std;//Struture of nodestruct Node{int data;Node *next;Node(int data){this->data=data;this->next=NULL;}};//function to find the nth node from//beginning in linked listint nthNodeFromBeginning(Node *head,int n){//if linked list is empty//return -1if(head==NULL)return -1;//node to store the head of//the linked listNode *temp=head;//varible to hold the count of nodesint count=0;//iterate till end of list or//count becomes nwhile(temp!=NULL){//increment the count//of nodescount++;//if count becomes n then//return the current node dataif(count==n)return temp->data;//move to the next nodeelsetemp=temp->next;}//if length of linked list//is less than n then return -1return -1;}int main(){Node *head=new Node(5);head->next=new Node(2);head->next->next=new Node(8);head->next->next->next=new Node(4);head->next->next->next->next=new Node(1);int n=3;int nthNode=nthNodeFromBeginning(head,n);if(nthNode==-1)cout<<"Nth node is not present \n";elsecout<<"Nth node is "<<nthNode<<"\n";return 0;}//Time Complexity: O(n)//Space Complexity:O(1)
No comments:
Post a Comment