整理一些面试可能会遇到的算法题目

将两个有序的单链表合并为一个有序的单链表，默认是按升序排列的。【两路归并排序（升序排列）  (平均/最差)时间复杂度O(NlogN)】

typedef struct _Node_t
{
    struct _Node_t *next;
    int data;
}Node;

Node *Merge(Node *head1, Node *head2)//时间复杂度：O(nlogn)
{
    Node *head = NULL;
    
    if (NULL == head1)
    {
        return head2;
    }

    if (NULL == head2)
    {
        return head1;
    }
   
    while ((NULL != head1) && (NULL != head2))
    {
        if (head1->data < head2->data)
        {
            head = head1;
            head->next = Merge(head1->next, head2);
        }
        else
        {
            head = head2;
            head->next = Merge(head1, head2->next); 
        }
    }

    return head;
}

判断单链表中是否有环，有的话找到环的入口点

定义两个指针slow, fast。slow指针一次走1个结点，fast指针一次走2个结点。如果链表中有环，那么慢指针一定会再某一个时刻追上快指针(slow == fast)。如果没有环，则快指针会第一个走到NULL。

class Node {
    public Node next;
    public Object data;

    public static int sequence = 0;
}

/**
     * 快慢指针
     * @param head
     * @return
     */
    public static boolean checkCircle(Node head) {
        Node fast = null;
        Node slow = null;

        fast = head;
        slow = head;
        while (true) {
            // 慢指针移动一步
            if (null != slow.next) {
                slow = slow.next;
            } else {
                return false;
            }

            // 快指针移动两步
            if (null != fast.next && null != fast.next.next) {
                fast = fast.next.next;
            } else {
                return false;
            }

            // 检查是否相遇
            if (slow == fast) {
                return true;
            }
        }
    }

定义两个指针p, q。p每走一个结点(即一步)，q则从头一直向后走，直到q走到NULL或p, q走到同一个结点但走过的步数不相同为止。此时q的步数就是环入口在结点中的位置。如果走到NULL则说明链表不存在环。

/**
     * 查找环的起点
     * @param head
     * @return 返回元素的索引，从0开始。没有找到返回-1
     */
    public static int findCircleEntry(Node head) {
        Node p = head; // 总是从头开始
        Node q = head;

        int pSteps = 0;
        int qSteps = 0;
        while (null != q.next) {
            q = q.next;
            ++qSteps;

            // p从头开始走
            while (null != p.next) {
                p = p.next;
                ++pSteps;

                // 当p与q指向同一个结点时
                if (p == q) {
                    // 如果走的步数不同，则这就是入口
                    if (pSteps != qSteps) {
                        return pSteps - 1;
                    } else {
                        // 走的步数相同，不是入口
                        break;
                    }
                }
            }

            p = head; // 回到头结点
            pSteps = 0;
        }

        // 其中有一个指针走到了头，说明没有环
        return -1;
    }

斐波拉契数列递归实现的方法如下:

int Funct( int n )
{
	if(n==0) 
		return 1;
	if(n==1) 
		return 1;
	retrurn Funct(n-1) + Funct(n-2);
}

判断一个字符串是不是回文

int IsReverseStr(char *aStr)
{
	
	if(aStr==NULL)
		return -1;

	int i,j;
    j=strlen(aStr);

    int found=1;
    for(i=0;i<j/2;i++)
    {
	     if(*(aStr+i)!=*(aStr+j-i-1)) 
	     {
	       found=0; 
	       break;
	     }
    }
    return found; 
}

6. 关键字 static 的作用是什么?
这个简单的问题很少有人能回答完全。在 C 语言中，关键字 static 有三个明显 的作用:
1). 在函数体，一个被声明为静态的变量在这一函数被调用过程中维持其值不 变。
2). 在模块内(但在函数体外)，一个被声明为静态的变量可以被模块内所用函 数访问，但不能被模块外其它函数访问。它是一个本地的全局变量。

3). 在模块内，一个被声明为静态的函数只可被这一模块内的其它函数调用。那 就是，这个函数被限制在声明它的模块的本地范围内使用。 

非 C++内建型别 A 和 B，在哪几种情况下 B 能隐式转化为 A?

a. class B : public A { ......} // B 公有继承自 A，可以是间接继承的
b. class B { operator A( ); } // B 实现了隐式转化为 A 的转化
c. class A { A( const B& ); } // A 实现了 non-explicit 的参数为 B(可以有其 他带默认值的参数)构造函数

d. A& operator= ( const A& ); // 赋值操作，虽不是正宗的隐式类型转换， 但也可以勉强算一个

快速排序：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数

void quickSort(int s[], int l, int r)  
{  
    if (l< r)  
    {        
        int i = l, j = r, x = s[l];  
        while (i < j)  
        {  
            while(i < j && s[j]>= x) // 从右向左找第一个小于x的数  
                j--;   
            if(i < j)  
                s[i++] = s[j];  
            while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数  
                i++;   
            if(i < j)  
                s[j--] = s[i];  
        }  
        s[i] = x;  
        quickSort(s, l, i - 1); // 递归调用  
        quickSort(s, i + 1, r);  
    }  
}