Remove a middle node of a singly linked which has odd number of nodes using a single pointer ?

Question

I am looking for sample code which can impress an interviewer.

Answer 1

int total = 0, mid = 0;

If (head->next)
       delelte_mid_node(head, &total, &mid);
else                // If only one node in list then no need to call function "delelte_mid_node"
    head = NULL;


void deleltemidnode(node *ptr, int *totalnode, int *mid)
{

        if (ptr == NULL)
        {
                *totalnode = *totalnode - 1;
                if (*totalnode % 2 == 0)
                        printf("\nNode is even in list\n");
                return;
        }
        *totalnode = *totalnode + 1;
        deleltemidnode(ptr->next, totalnode, mid);
        if(*totalnode %2 != 0)
        {
                *mid = *mid + 1;
                if(*mid == ((*totalnode + 2) / 2))
                {
                        ptr->next = ptr->next->next;
                }
        }
}

Logic is right.
But here is memory leak because i did not free the memory of deleted node.

Answer 2

You have to traverse, no way

public void findAndDeleteMiddleNode() {
    Node n1 = headNode;
    Node n1Prev = NULL;
    Node n2 = headNode;
    while(n2.getNext() != null && n2.getNext().getNext()!= null) {
        n1Prev = n1; 
        n1 = n1.getNext();
        n2 = n2.getNext().getNext();
    }

    System.out.println("middle node is "+n1.getKey());
   // Now remove 
   n1Prev.setNext(n1.getNext());
   delete n1;
}

Comments

sorry missed you word single pointer :(

---

sir there is nothing like a pointer in java. but in these two lines of code
 n1 = n1.getNext();
 n2 = n2.getNext().getNext();

you are assigning the next node in n1 and next to next node in n2, which are two different memory address, so they are acting as two pointers. but according to the question we have to do it using single pointer....... sir correct me if i am wrong.

---

Yes you are correct, forgot to work on this....