CareerCup

1. Have two pointers ptr1 and ptr2 pointing to head of linked list
2. Traverse one pointer say ptr2 to distance n from head
3. Now, traverse both
4. When ptr2 reaches the tail, ptr1 is at distance "n" from the tail of linked list

Need to do validation like
1. null check,
2. n might be greater than the length of linked list,
3. loop check and etc.,

void deleteNthfromLast(struct node **p)
{
     struct node *start,*t1,*temp;
     int n;
     start = *p;
     printf("Enter the nth element from end to be deleted = ");
     scanf("%d",&n);
     while(n && start) //
     {
            start = start->next;
            n--;
     }                
     
     if(!start)  //if the input provided is less than the linklist size
     {
               printf("\nWrong input provided");
               return;
     }               
     
     if(!start->next) //frist node to be deleted
     {
              temp = *p;
              *p = (*p)->next;
              free(temp);
              return;
     }              
     start = start->next; //t1 should point to one node behind the actual node to delete
     t1 = *p;
     
     while(start->next)
     {
           start = start->next;
           t1 = t1->next;
     }
     temp = t1->next;
     t1->next = t1->next->next;
     free(temp);
     return;
}

#include<iostream>
using namespace std;

struct node
{
    int k;
    node *next;
};
node *HEAD = NULL;

node* create(int v)
{
    node *temp = new node;
    temp->k = v;
    temp->next = NULL;
    return temp;
}

void insert(node *n)
{
    if(HEAD == NULL)
        HEAD = n;
    else
    {
        node *m = HEAD;
        while(m->next != NULL)
        {
            m = m->next;
        }
        m->next = n;
    }
}

void show()
{
    node *m = HEAD;
    while(m != NULL)
    {
        cout<<m->k<<"->";
        m = m->next;
    }
    cout<<"NULL";
}

void delete_Nth(int v)
{
    node *m = HEAD;
    node *prev = HEAD;
    bool continu = true;
    while(continu && m!= NULL)
    {
        int i;
        node *n = m;
        for(i = 0; i < v && n != NULL ;)
        {
            i++;
            n = n->next;
        }

        if((i == v) && (n == NULL))
        {
            if(m == HEAD)
                HEAD = m->next;
            else
                prev->next = m->next;

            delete m;
            continu = false;
        }
        else
        {
            prev = m;
            m = m->next;
        }
    }
    show();
}

int main()
{
    char ch = 'y';
    int v;
    do
    {
        cout<<"Enter new key : ";
            cin>>v;
        insert(create(v));
        cout<<"Enter more (y/n) ? : ";
        cin>>ch;
    }while(ch == 'y');

    cout<<"\n\nEnter the last nth node number to delete : ";
    cin>>v;
    delete_Nth(v);
    return 0;
}

Node* DeleteNthLast(Node* head, int n)
{
	Node* temp = head;
	Node* t = head;
	int m = 0;
	if( head== NULL )
		return head;
	while( temp != NULL )
	{
		temp = temp->next;
		if( m >= n+1 )
			t = t->next;
		m++;
	}
	if( m == n)
		return head;

	temp = t->next;
	t->next = t->next->next;
	delete(temp);
	return head;
}

#include<iostream>
using namespace std;

typedef struct node{
	int data;
	struct node* next;
}* Node;

Node createSLL(const int& n){
	if(n <= 0)
		return NULL;
	
	Node head = (Node) malloc(sizeof(struct node));
	head->data = 1;
	head->next = NULL;
	
	Node tempHead = head;
	for(int i = 2; i <= n; i++){
		Node tempNode = (Node) malloc(sizeof(struct node));
		tempNode->data = i;
		tempNode->next = NULL;
		tempHead->next = tempNode;
		tempHead = tempNode;
	}
	return head;
}

void printSLL(Node head){
	Node tempHead = head;
	while(tempHead){
		cout << tempHead->data << " ";
		tempHead = tempHead->next;
	}
	cout << endl;
	return;
}

bool deleteNthElement(Node& head, const int& n){
	if(head == NULL || n <= 0)
		return false;
	
	Node tempHead = head;
	int count = 0;
	Node p, q = tempHead;
	while(q != NULL && count++ < n)
		q = q->next;

	if(count == n+1){
		p = tempHead;
		while(q->next != NULL){
			p = p->next;
			q = q->next;
		}
		p->next = p->next->next;
		return true;
	}else if(count == n){
		head = head->next;
		return true;
	}else{
		return false;
	}
}

int main(int argc, char* args[]){
	Node head = createSLL(8);
	printSLL(head);
	
	if(deleteNthElement(head, 8)){
		cout << "delete success..." << endl;
		printSLL(head);
	}else{
		cout << "fail to delete node..." << endl;
	}
	return 0;

}