CareerCup

following checks should be done before proceeding

null check on list
N <= 0, throw custom exception
N == 1, we need to delete all the nodes
Circular check using Floyd's cycle detection method or any other method

if not circular, its easy

int count = 0;
            
            while (current != null)
            {
                count++;

                if (count % n == 0)
                {
                    current.prev.next = current.next;

                    if (current.next != null)
                        current.next.prev = current.prev;
                }

                current = current.next;

}

or we need to find the start of the loop and check for it when we iterate through the list and delete

The question is quite unclear to me,

1. is it circular dll. ?
2. Delete every Nth node means delete the nodes untill only one node is left.
3. If you delete Nth node then your next count should start from (N+1) th node?

is this circular doubly linked list?

Delete the Nth node and the next (N-1)th node , next (N-2)th node and so on unless you come to end.

struct doubly_link_node
{
	struct doubly_link_node *next;
	struct doubly_link_node *prev;
	int data;
};

void remove_nth_doubly_link_node(struct doubly_link_node **head, unsigned int n)
{
	struct doubly_link_node *curr = *head;

	while (n-- && curr != NULL) {
		curr = curr->next;
	}

	if (curr != NULL) {
		if (curr->prev != NULL) {
			curr->prev->next = curr->next;
		} else {
			*head = curr->next;
		}

		if (curr->next != NULL) {
			curr->next->prev = curr->prev;
		}

		free(curr);
	}
}

Q1: Every nth node from start or from end or both???

Q2[just a corner case :)]: Do we need to delete all nth node from initial condition of given list
OR
Do we need to delete all nth node at any stage
for ex if if have
1..2..3..4..5..6..
I have to delete each 3rd node
so I deleted 3rd node and list became
1..2..4..5..6..
now again deleted 3rd node
1..2..5..6..
and so on
1..2..

void getNthNode(Node temp,int count,int level)
{
     if(temp!=null)
	 {
	    if(count==level)
		{
		      Print(temp.data);
			   getNthNode(temp.next,1,level-1);
		}
		else
		{
		    getNthNode(temp.next,count+1,level);
		}
	 }

}

getNthNode(head,1,N);

Please some one let me know if the above code works or not.

Sorry for posting it multiple times. I updated the code to delete the every Nth node.

void getNthNode(Node temp,int count,int level)
{
     if(temp!=null)
	 {
	    if(count==level)
		{
		      temp.prev.next=temp.next;
			  temp.next.prev=temp.prev;
			  getNthNode(temp.next,1,level-1);
		}
		else
		{
		    getNthNode(temp.next,count+1,level);
		}
	 }

}

getNthNode(head,1,N);

Please some one let me know if the above code works or not.

public void deleteNthNode(Node head, int N) {
if ( head == null )
return;
if ( N == 1 ) {
head = head.next;
head.prev = null;
}

Node node = head;
for ( int i = 0; i < N && node != null; i++ )
node = node.next

if ( node == null )
return;
if ( node.next == null ) {
node.prev.next = null;
return;
}

node.prev.next = node.next;
node.next.prev = node.prev;
}

currN = head;
currN2=taill;
pos=0;
ilen=len(dlist); npos=ilen;
while(currN != null)||(pos<=ilen/2)
	if(pos%reqPos) == 0
		(currN->prev)->next) = currN->next;
		(currN->next)->prev) = currN->prev;
	if (npos%reqPos) == 0
		(currN2->prev)->next) = currN2->next;
		(currN2->next)->prev) = currN2->prev;
	currN = currN->Next;
	currN2 = currN2->Next;
	pos++;
	npos--;

void deleteNthNode(LNODE *head, int n)
{
LNODE *p = NULL;
LNODE *q = NULL;
int i;

if(head == NULL)
return;
if(n == 0)
return;

p = head->next;
for(i=n-1; i>0 && p!=NULL; i--)
{
p = p->next;
}


if(p == NULL)
return;
if(p != NULL)
{
p->pre->next = NULL;
p->pre = NULL;

q = p->next;
while(q != NULL)
{
free(p);
p = q;
q = p->next;
}
}
}

public class DoubleLinkedList {

	private class Node{
		
		int data;
		Node prev;
		Node next;
		
		public Node(int d)
		{
			data=d;
			prev=null;
			next=null;
		}
		
	}
	
	Node first;
	Node last;
	
	public void insert(int d)
	{
		Node newNode= new Node(d);
		
		if(first==null)
		{
			first=newNode;
			last=newNode;
			return;
		}
		
		last.next=newNode;
		newNode.prev=last;
		last=newNode;
	}
	
	public void display()
	{
		Node current=first;
		while(current!=null)
		{
			System.out.println(current.data);
			current=current.next;
		}
	}
	
	public void deleteNthNode(int N)
	{
		
		Node current=first;
		
		while(current.next!=null)
		{
			for(int i=1;i<N;i++){
				
				if(current.next!=null)
					current=current.next;
				else
					break;
			}
			
			if(current.next==null)
			{
				current.prev.next=null;
				current.prev=null;
				return;
			}
			
			current.prev.next=current.next;
			current.next.prev=current.prev;
			
			current=current.next;
			
		}
	}
	public static void main(String[] args) {
		
		DoubleLinkedList dll= new DoubleLinkedList();
		
		dll.insert(1);
		dll.insert(2);
		dll.insert(3);
		dll.insert(4);
		dll.insert(5);
		dll.insert(6);
		
		dll.deleteNthNode(3);
		dll.display();
	}

}

private void deleteEveryNthNode(int i) {
		
		System.out.println("####Deleting every "+i+"th Node......");

		LinkedList temp=head;
		int count=1;
		if(i<=0)
			return;
		else if(head==null)
			return;
		else if(i==1){
			head=null;
			return;
		}else{
			
			while(temp!=null){
				LinkedList p=temp;
				if((count+1)%i==0){
					
					if(p.next==null)
						p=null;
					else if(p.next.next==null)
						p.next=null;
					
					else if(p.next.next!=null)
					p.next=p.next.next;
					
					count++;
				}
				
				temp=temp.next;
				count++;
				
			}
			
		}
		
		
	}

void deletenth(dnode **headref, int n)
{
    int count=1;
    while(count!=(n+1))
    {
        dnode *tmp=*headref;
        if(tmp->next==NULL)  //if you reach the last element
        {
            *headref=NULL;
        }
        else
        {
            tmp->next->prev=NULL;
            *headref=tmp->next;
        }
        delete(tmp);
        count++;
    }
}