The problem is as follows:
Find the nth node from the end of a singly linked list.
Sample Input : 2->1->5->4->3 and n = 3
Sample Output : 5
'''Complexity Space: O(n) and Time: O(1)''' class Node: def __init__(self,data): self.data = data self.next = None def setData(self,data): self.data = data def getData(self): return self.data def setNext(self, next): self.next = next def getNext(self): return self.next class LinkedList: def __init__(self): self.head = None def isEmpty(self): return self.head == None def insertAtBeg(self,item): node = Node(item) node.setNext(self.head) self.head = node def length(self): current = self.head count = 0 while current != None: count += 1 current = current.getNext() return count def search(self,item): found = False current = self.head while current != None and not found: if current.getData() == item: found = True else: current = current.getNext() return found def insertAtEnd(self,item): current = self.head while current.getNext() != None: current = current.getNext() node = Node(item) current.setNext(node) def insertBeforeItem(self,inItem,item): current = self.head previous = None found = False stop = False while current != None and not found and not stop: if current.getData() == item: found = True stop = True else: previous = current current = current.getNext() node = Node(inItem) previous.setNext(node) node.setNext(current) def insertAfterItem(self,inItem,item): current = self.head found = False stop = False while current != None and not found and not stop: if current.getData() == item: found = True stop = True else: # previous = current current = current.getNext() successor = current.getNext() node = Node(inItem) current.setNext(node) node.setNext(successor) def printList(self): current = self.head while current != None: print current.getData() current = current.getNext() def remove(self,item): found = False current = self.head previous = None while current.getNext() != None and not found: if current.getData() == item: print current.getData() print previous.getData() found = True previous.setNext(current.next) else: previous = current current = current.getNext() def nthNodeFromEnd(self,n): if self.isEmpty(): print "There are no items in the list" return if n > self.length(): print "N is greater than the lenght of the list and is not possible to fetch it" return current = self.head previous = self.head count = 0 while count < n and current != None: count += 1 current = current.getNext() while current != None: previous = previous.getNext() current = current.getNext() return previous.getData() if __name__ == "__main__": ll = LinkedList() ll.insertAtBeg(1) ll.insertAtBeg(2) ll.insertAtEnd(3) ll.insertBeforeItem(4, 3) ll.insertAfterItem(5, 1) print "The linked list is as follows:" ll.printList() print "\n\n" print "The 2nd item from the end is:",ll.nthNodeFromEnd(2) print "The 3rd item from the end is:", ll.nthNodeFromEnd(3)
Pingback: Linked Lists | codeatsociallywired
//same problem implemented by c++
#include
#include
#include
using namespace std;
struct node{
int i_val;
struct node * next;
};
node *root=NULL;
node * Getnode(int &i_val){
node *temp=( node *)malloc ( sizeof (struct node ) );
// std::cout<<temp<i_val=i_val;
temp->next=NULL;
return temp;
}
bool Insert( node *head , int &i_value ){
if( head == NULL ) root=Getnode( i_value );
else {
while( head->next != NULL ) head=head->next;
head->next=Getnode(i_value );
}
return true ;
}
bool Find ( node *head , int i_position ){
std::cout<<"Find for position ="<<i_position<<std::endl;
int count=1;
node *temp1=head;
node *temp2=head;
while ( count next;
count++;
}
if( temp1==NULL ) return false;
while( temp1 != NULL ){
temp1=temp1->next;
temp2=temp2->next;
}
std::cout<<"Position ="<<i_position << "Data = "<i_val<>i_number;
std::cin>>i_find;
int i_iterator=1;
int i_temp;
while ( i_iterator >i_temp;
if ( !Insert ( root , i_temp ) ) {
std::cout<<"memory full"<<std::endl;
exit(EXIT_FAILURE);
}
}
node *temp=root;
std::cout<<"Data in linked list\n";
while( temp !=NULL ) { std::cout<i_val<“; temp=temp->next; }
std::cout<<"NULL"<<std::endl;
if ( !Find( root , i_find ) ) std::cout<<"OUT of SIze\n";
return 0;
}