复习一下<程序员面试攻略>,并记录一些心得.

链表:
1. 找到单链表中倒数第m个元素
方法：使用两个指针，这两个指针相距m个元素，然后使得两个指针同步前进，当后一个指针到空时，前一个指针即为倒数第m个元素
实现：
elem* FindMToLastElem(elem* head, int m)
{
    elem* current, mbehind;
    current = head;
    for(int i=0; i<m; i++)
    {
        if(current->next)
        {
            current = current->next;
        }
        else
        {
            return NULL;
        }
    }
    
    mbehind = head;
    while(current->next)
    {
        current = current->next;
        mbehind = mbehind->next;
    }

    return mbehind;
}

2. 判断一个链表为循环链表还是非循环链表

方法：使用快慢指针，快指针每次走两步，慢指针每次走一步，若快指针到达NULL，则为非循环链表，若快指针超过了慢指针，则为循环链表
实现：
int determin_termination(node* head)
{
    node* fast, slow;
    if(!head || !(head->next))
    {
        return 0;
    }
    fast = head->next->next;
    slow = head->next;
    while(1)
    {
        if(!fast || !(fast->next))
        {
            return 0;
        }
        else if(fast == slow || fast->next == slow)
        {
            return 1;
        }
        else
        {
            fast = fast->next->next;
            slow = slow->next;
        }
    }
}

树和图:
1. 二叉树前序遍历的非递归算法
方法：使用堆栈
实现：
void PreorderTraversal(node* head)
{
    elem* stack;
    CreateStack(&stack);
    Push(&stack, head);
    
    node* pNode;
    while(Pop(&stack, &pNode)
    {
        if(NULL != pNode)
        {
            printf("%d\n", pNode->value);
            Push(&stack, pNode->right);
            Push(&stack, pNode->left);
        }
    }
    DeleteStack(&stack);
}

数组和字符串:
1. 高效删除特定字符
方法：每次删除字符时不在数组中移动字符串，而是直接拷贝到之前扫描过的位置中。另外采用数组来减少字符串比较次数。
void RemoveChars(char str[], char remove[])
{
    // create an array for remove characters
    char removeArray[256];
    for(int i=0; i<256; i++)
    {
        removeArray[i] = 0;
    }
    int src = 0;
    while(remove[src])
    {
        removeArray[remove[src]] = 1;
        src++;
    }
    int dest = 0;
    src = 0;
    do
    {
        if(!removeArray[remove[src]])
        {
            str[dest++] = str[src];
        }
    }while(str[src++]);
    
}

2. 颠倒单词出现的次序
Do or do not, there is no try. 转换为 try. no is there not, do or Do
方法：先将整个字符串颠倒，再将新字符串中的每个单词颠倒

3. 编写字符串和数字相互转换函数
int Str2Int(char* str)
{
    int num = 0, neg = 1, i = 0;
    if(str[0] == '-')
    {
        neg = -1;
        i = 1;
    }
    
    while(str[i])
    {
        num = num * 10 + str[i++] - '0';
    }
    num = num * neg;
    return num;
}

void Int2Str(int num, char str[])
{
    int neg = 1;
    if(num < 0)
    {
        num *= -1;
        neg = -1;
    }
    
    int i = 0;
    do
    {
        str[i++] = num % 10 + '0';
        num = num / 10;
    }while(num)

    if(neg == -1)
    {
        str[i++] = '-';
    }
    str[i] = 0;
    
    for(int j = 0; j < i/2; j++)
    {
        str[j] = str[i-1-j];
    }
    
}