cpppro

Archive for the ‘Algorithms’ Category

C/C++ Interview algorithms

In Algorithms, Data Structures in C/C++, Question Patterns on April 17, 2007 at 10:35 pm

1. Reverse a singly linked list

//
// iterative version
//
Node* ReverseList( Node ** List )
{
  Node *temp1 = *List;
  Node * temp2 = NULL;
  Node * temp3 = NULL;

  while ( temp1 )
  {
    //set the head to last node
    *List = temp1;

    // save the next ptr in temp2
    temp2= temp1->pNext;

    // change next to privous
    temp1->pNext = temp3;
    temp3 = temp1;
    temp1 = temp2;
  }

  return *List;
}

2. Delete a node in double linked list

void deleteNode(node *n)
{
  node *np = n->prev;
  node *nn = n->next;
  np->next = n->next;
  nn->prev = n->prev;
  delete n;
}

3. Sort a linked list

//sorting in descending order
struct node
{
  int value;
  node* NEXT;
}
//Assume HEAD pointer denotes the first
//element in the linked list
//only change the values? don't have to
//change the pointers
Sort( Node *Head)
{
  node* first,second,temp;
  first= Head;
  while(first!=null)
  {
    second=first->NEXT;
    while(second!=null)
    {
      if(first->value value)
      {
        temp = new node();
        temp->value=first->value;
        first->value=second->value;
        second->value=temp->value;
        delete temp;
      }
      second=second->NEXT;
    }
    first=first->NEXT;
  }
}

4. Reverse a string

void ReverseString (char *String)
{
  char *Begin = String;
  char *End = String + strlen(String) - 1;
  char TempChar;

  while (Begin < End)
  {
    TempChar = *Begin;
    *Begin = *End;
    *End = TempChar;
    Begin++;
    End- -;
  }
}

5. Insert a node a sorted linked list

void sortedInsert(Node * head, Node* newNode)
{
  Node *current = head;

  // traverse the list until you find
  //item bigger the new node value
  //
  while ((current!= NULL) &&
         (current->data data))
  {
    current = current->next;
  }
  //
  // insert the new node before the big item
  //
  newNode->next = current->next;
  current = newNode;
}

6. Covert a string to upper case

void ToUpper(char * S)
{
  while (*S!=0)
  {
    *S=(*S >= 'a' && *S <= 'z')?(*S-'a'+'A'):*S;
    S++;
  }
}

7. Multiple a number by 7 without using * and + operator.

Reversing a double linked list

In Algorithms, C Tidbits, Data Structures in C/C++ on March 30, 2007 at 5:43 pm

refer double linked list post for information about double linked list. Here in this post we will be discussing about reversing a double linked list.

Here is the pictorial representation of our algo…
reversing double linked list

in our routine we will swap our next, prev pointers of nodes to reverse the double linked list… this routine capable of reversing entire list for given any node in the double linked list.

The below routine takes input as any node in double linked list and reverse the entire double linked list and returns same node pointer.

please refer http://www.refcode.net/2013/02/reversing-double-linked-list.html

Reversing a single linked list using stack

In Algorithms, C Tidbits, Data Structures in C/C++ on March 30, 2007 at 3:40 pm

Here is the routine for reversing single linked list using a stack, for reversing linked list using pointers, see the earlier post. For reversing linked list recursively visit this post. This routine takes a single linked list as argument and reverse it and returns back the head node to the reversed list.

please refer http://www.refcode.net/2013/02/reversing-single-linked-list-using-stack.html

Reversing single linked list recursively

In Algorithms, C Tidbits, Data Structures in C/C++ on March 30, 2007 at 3:30 pm

Here is the routine for reversing single linked list recursively, for reversing iteratively see the earlier post . For reversing circular single linked list visit this post. This routine takes a single linked list as argument and reverse it and returns back the head node to the reversed list.

 

please referĀ http://www.refcode.net/2013/02/reversing-single-linked-list-recursively.html