misc

//4.linkedlist有无环 （fast/slow runner）

typedef struct Node{
int value;
struct Node* next;
}node;

bool hasLoop(node* ll)
{
node *fast, *slow;
fast = slow = ll;
bool isLoop=false;
while(fast!=NULL)
{
if(fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
if(fast == slow) return true;
}

return isLoop;
}

node * mToLast(node * ll, int m)
{
node * fast, *slow;
fast = slow = ll
for(int i=0; i<m; i++)
{
if(fast == NULL) return NULL;
fast = fast->next;
}
while(fast != NULL)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}

node* mToLastBST(node *root, int m, int *cnt)
{
node *tmp;
if(!root) return NULL;
if(root->right)
{
tmp=mToLastBST(root->right, m, cnt);

}
if(*cnt == m) return tmp;
else *cnt +=1;

if(*cnt == m) return root;
if(root->left)
{
tmp=mToLastBST(root->left, m, cnt);
}
if(*cnt == m) return tmp;
else return NULL;
}

void createList(node **head)
{
*head = NULL;
return ;
}

void deleteList(node **head)
{
node* ptr1, *ptr2;
ptr1 = *head;
while(ptr1)
{
ptr2 = ptr1->next;
free(ptr1);
ptr1 = ptr2;
}
return;
}

void listDeleteNode(node **head, node * toDel)
{
node *ptr, *tmp;
//if it is head
if(*head == toDel)
{
head = *head->next;
free(toDel);
return;
}
ptr = *head;
while(ptr->next != toDel && ptr->next != NULL)
{
ptr = ptr->next;
}
if(ptr->next == toDel)
{
ptr->next = toDel->next;
free(toDel);
}
return;
}

//两个字符串，求出unique characters，即只出现在一个string中的char
//（array[26]，用0-3标记）
vector<char> uniqueChars(char* a, char* b)
{
int charCnt[26];
for(int i=0; i<26; i++) charCnt[i] = 0;

char *tmp;
tmp = a;
while(tmp!='\0')
{
if(charCnt[*tmp-'a'] == 0) charCnt[*tmp-'a'] = 1;
tmp++;
}
//find unique chars
tmp = b;
while(tmp!='\0')
{
if(charCnt[*tmp-'a'] == 0) charCnt[*tmp-'a'] = 2;
if(charCnt[*tmp-'a'] == 1) charCnt[*tmp-'a'] = 3;
tmp++;
}
vector<char> result = new vector<char>;
for(int i=0; i<26; i++)
{
if(charCnt[i] == 1 || charCnt[i] == 2) result.push_back((char)(i+(int)'a'));
}
return result;
}

/*tree mirror
root
l r
ll lr rl rr

root
r l
rr rl rl ll
*/

void treeMirror(node * root)
{


if(root->left) treeMirror(root->left);
if(root->right) treeMirror(root->right);

swap(root->left, root->right);
return;

}


int occurrance(vector<int> & seq, int n)
{
//assuming n does exist in seq
//find the beginning where seq[c]==n
int begin, end;
int a, b, c;
a = 0;
b = seq.size()-1;
c = (a+b)/2;
while(a<b)
{
if(n<seq[c] || (n==seq[c] && n==seq[c-1])) {b=c-1;}
else if(n>seq[c]) {a=c+1;}
else break;
}
begin = c;

//find the end where seq[c]==n
a = 0;
b = seq.size()-1;
c = (a+b)/2;
while(a<b)
{
if(n<seq[c]) {b=c-1;}
else if(n>seq[c] || (n==seq[c] && n==seq[c+1])) {a=c+1;}
else break;
}
end = c;
return end-begin+1;
}