面试题一般会有普通方法和高级方法，高级方法无疑会大大的加分！
题目一：快速找到未知长度单链表的中间节点（腾讯面试题）
普通解法
- 思路
首先遍历一遍单链表以确定单链表的长度。然后再次从头结点出发循环L/2次找到单链表的中间节点。
算法复杂度为：O(L+L/2) = O(3L/2)
高级解法
- 思路
利用快慢指针原理：设置两个指针*search和*mid都指向单链表的头节点。其中*search的移动速度是*mid的2倍。当*search指向结尾节点的时候，mid正好在中间了。这也是标尺的思想。 - 代码实现
#include <stdio.h>
#define OK 1;
#define ERROR 0;
#define TRUE 1;
#define FALSE 0;
#define MAXSIZE 20 /* 定义线性表可能达到的最大长度 */
typedef int ElemType;
typedef struct {
ElemType data[MAXSIZE];
int length;
}SqList;
typedef int Status;
// 单链表
typedef struct Node{
ElemType data; // 数据域
struct Node * next; // 指针域
}Node;
// 取别名
typedef struct Node * LinkList;
/**
* 用快慢指针快速找到未知长度单链表的中间节点
*/
Status GetMidNode(LinkList L, ElemType * e){
LinkList search, mid;
mid = search = L;
while (search->next != NULL) {
//search的速度是mid的两倍
if (search->next->next != NULL) {
search = search->next->next;
mid = mid->next;
}else{
search = search->next;
}
}
// 中间节点
*e = mid->data;
return OK;
}
