citpyrc
BAN USERThis will work perfectly with single parens if you
return false
if the count goes negative at any time. Plus if you have a
char prev='\0'
having the previous paren you can match any closing paren with the corresponding prev counterpart and return false if violation occur.
- citpyrc January 22, 2013Would recommend you to draw the linked list example given and understand.
void step_reverse_list(struct node **head,int step)
{
struct node *prev=NULL,*will_visit_next,*iterator=*head,start_node;
struct node *sixth_prev_node=&start_node,*third_prev_node; //create a fake start_node so as to get the start node inside the general loop
int n=step;
while(iterator->next!=NULL)
{
if(n%step==0)
third_prev_node = iterator; //store this node, as we will need to modify its next later
if(n%step==1)
{
sixth_prev_node->next=iterator; //this is the node which should be pointed by the 6th previous node
sixth_prev_node = third_prev_node; //transfer the 3rd previous node
n = step+1; //increase step by n+1 as step -- occurs in the end
}
will_visit_next = iterator->next;
iterator->next = prev;
prev = iterator;
iterator = will_visit_next;
n--;
}
iterator->next=prev; //normal reversal technique
sixth_prev_node->next = iterator; //this is the node that the 6th previous or the node between the 3rd and 6th prev should point to (originnally the last node)
third_prev_node->next = NULL; //the 3rd previous or 2nd or previous node should be the last element in the new linked iterator
*head = start_node.next; //we now modify the head to be the next pointer of the fake start_node we created for the sake of generality
}
I may not be sure, but the following part worked with one example at least. I didn't have time to testit with other examples. It is basically BFS.
Structure of the binary search tree used modified for BFS
typedef struct bsearch_tree
{
int key;
int level;
struct bsearch_tree *parent;
struct bsearch_tree *left;
struct bsearch_tree *right;
}BSTREE;
The function
BSTREE* leftmost_right_cousin(BSTREE* T,int item)
{
QUEUE Q;
BSTREE *u,*this_parent;
int find=0,find_level;
if(T!=NULL)
{
init_queue(&Q);
T->level = 0;
enqueue(&Q,T);
while(!is_empty(&Q))
{
u = dequeue(&Q);
if(find) //we have found the node whose cousin we are trying to find
{
if(u->level==find_level && u->parent != this_parent) //the cousin will be in the same level of the tree but its parent will be different
return u; //return the first node satisfying the condition
else if(u->level > find_level) //we are looking at some node at a deeper level than the required node. So we must not have found any cousin (to the right of the given node and having a different parent)
return NULL;
}
if(u->key == item) //found the node whose cousin we are looking for
{ find = 1; find_level = u->level; this_parent = u->parent;}
if(u->left!=NULL)
{
u->left->level = u->level + 1; //basic BFS algo, Since left node is put first into Q and Q being FIFO we will be dequeuing nodes from left to right in a particular level
u->left->parent = u;
enqueue(&Q,u->left);
}
if(u->right!=NULL)
{
u->right->level = u->level + 1;
u->right->parent = u;
enqueue(&Q,u->right);
}
}
return NULL; //we didn't find the node whose cousin we are looking for, so the given node doesn't exist in the first place
}
return NULL; //the tree has no nodes at all
}
As already stated in the comment, since we are using a Queue in BFS and we are enquing nodes from left to right in a particular level, I don't think we will require to mark the nodes Left or Right, doing which will actually require different implementations for the given node being Left/Right.
*The fn provided is subject to correction.
@sw, the only way there can be any duplicates without violating the sorted order property is two same numbers being consecutive which is checked by the <= operator. Otherwise duplicates would violate the sorted order property.
- citpyrc February 07, 2013