南京三星面试准备2--链表
1、复杂链表的复制
2、给定单链表，检测是否有环。
使用两个指针 p1,p2 p1,p2 p1,p2 p1,p2 p1,p2 p1,p2 从链表头开始遍历， p1 每次前进一步， p2 每次前进两步。如果 每次前进两步。如果 每次前进两步。如果 每次前进两步。如果 每次前进两步。如果 每次前进两步。如果 p2 到达链表尾部，说明无环否则 达链表尾部，说明无环否则 达链表尾部，说明无环否则 达链表尾部，说明无环否则 达链表尾部，说明无环否则 达链表尾部，说明无环否则 达链表尾部，说明无环否则 p1 、p2 必然会在某个时刻相遇 (p1==p2)(p1==p2)(p1==p2)(p1==p2)(p1==p2)(p1==p2)(p1==p2)(p1==p2)，从而检测到链表中 ，从而检测到链表中 ，从而检测到链表中 ，从而检测到链表中 ，从而检测到链表中 有环。
3、给定单链表，如果有环的话请返回从头结点进入第一个节。
我们可以检查链表中是否有环。如果那么 p1、p2 重合点 p 必然在环中。 从 p 点断开环，方法 为： p1=p, p2=p>next , p>next, p->next=NULL。此时，原单链表可以看作两 条单链表，一从 条单链表从 head 开始，另一条从p2开始，可以运用寻找两个单链表的公共节点来做。
4.(1) 编写实现链表排序的一种算法。说明为什么？
Merge sort
(2)编写实现数组排序的一种算法。说明为什么?
quick sort
(3)实现函数strstr
包含文件：string.h函数名: strstr函数原型：extern char *strstr(char *str1, char *str2);功能：从字符串str1中查找是否有字符串str2，如果有，从str1中的str2位置起，返回str1中str2起始位置的指针，如果没有，返回null。返回值：返回该位置的指针，如找不到，返回空指针。