Getting nth node of a linked list from the end

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

2 thoughts on “Getting nth node of a linked list from the end

  1. Pingback: Linked Lists | codeatsociallywired

  2. //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;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s