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)
Advertisements
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;
}