C++ Interview algorithms questions

1) Reverse a single linked list

Answer code:

Node* ReverseList(Node ** List)       // Provide a link list
{
      // Declare 3 pointer variable
      Node *head   =  *List; 
      Node *temp2 = NULL;
      Node *temp3 =NULL;

      while(head)
     {
          *List = head; // set the head to last node
           temp2 = head->pNext;     // save the next ptr in the temp2
           head->pNext = temp3;     // change next to previous
           temp3 = head;
           head = temp2; 
      }
}

Diagram detail:

    List linked list  [ 1 ] ->;   [ 2 ] ->;   [ 3 ] ->;
               1)         *List= head;  // Set head point to the last node
               2)         temp2 = head->pNext; //   saved as temp2   ( temp2 point to ptr2 )
               3)         head ->pNext = temp3;  // at the first round, it point to the null  
               4)        temp3 = head;   // set temp3 as head   ( temp3 point to ptr1)
               5)        head = temp2;   // get back the temp2 location ( head point to ptr2 ) 
               second round
               6)         *List= head;  // Set head point to the last node ( head to ptr2 )
               7)         temp2 = head->pNext; //   saved as temp2   ( temp2 point to ptr3 )
               8)         head ->pNext = temp3;  // at the second round, it point ptr 1  
               9)         temp3 = head;   // set temp3 as head   ( temp3 point to ptr2 )

               10)        head = temp2;   // get back the temp2 location ( head point to ptr3 ) 
             
        
2) Delete a node in double linked list

Answer:
        Doubly linked lists are like singly linked lists, except each node has two pointers -- one to the next node, and one to the previous node. This makes life nice in many ways:

• You can traverse lists forward and backward.
• You can insert anywhere in a list easily. This includes inserting before a node, after a node, at the front of the list, and at the end of the list.
• You can delete nodes very easily.

    void deleteNode( Node *n)
    {
      node *np = n->prev;    // set np pointer to the n->prev
      node *nn = n->next;    // set nn pointer to the n->next
      np->next = n->next;    // skip n node
     nn->prev = n->prev;    // skip n node
     delete n;
    } 

    Diagram:

    [  np ]  ->;  [ n  ] ->;  [ nn  ] ->;


 3)  Sort a linked list
 
     // Sorting in descending order
     struct node
    {
           int value;
           node* NEXT;
    }

   // start the sorting
   sort (node *head)     // pass the linklist head to the function
   {
      node* first, second, temp;   // define 3 nodes variable
      first = head;   // set first as head
      while(first!=null)   // check first is not empty link list
      {
               second = first->NEXT;
               while(second !=null )   // check the end of linked list  
               {
                         if(first->value  > second->value)
                         {
                                 temp = new node();  // allocate memory
                                temp->value = first->value;
                                first->value = second->value;
                                second->value = temp->value;
                                delete temp;   // release the memory
                          }
                         second= second->NEXT;
                }
               first=first->NEXT;
       } 
   }


4) Reverse a string
 
Answer:

     void ReverseString ( char *String)
     {
            char *Begin = String;    // set up 2 pointer, one for the beginning of the spring address
            char *End = String + strlen(String) -1;   // point to the end of the spring address
            char tempChar ='\0';    // end of line
  
            while (Begin < End)
           {
                   TempChar = *Begin;
                   *Begin = *End;
                   *End = *TempChar;
                   Begin++;
                   End--;
            }      
     }