面試題一般會(huì)有普通方法和高級(jí)方法错洁，高級(jí)方法無(wú)疑會(huì)大大的加分滨达！
題目一：快速找到未知長(zhǎng)度單鏈表的中間節(jié)點(diǎn)（騰訊面試題）
普通解法
- 思路
首先遍歷一遍單鏈表以確定單鏈表的長(zhǎng)度强经。然后再次從頭結(jié)點(diǎn)出發(fā)循環(huán)L/2次找到單鏈表的中間節(jié)點(diǎn)厂榛。
算法復(fù)雜度為：O(L+L/2) = O(3L/2)
高級(jí)解法
- 思路
利用快慢指針原理：設(shè)置兩個(gè)指針*search和*mid都指向單鏈表的頭節(jié)點(diǎn)吕粹。其中*search的移動(dòng)速度是*mid的2倍族扰。當(dāng)*search指向結(jié)尾節(jié)點(diǎn)的時(shí)候厌丑，mid正好在中間了定欧。這也是標(biāo)尺的思想。 - 代碼實(shí)現(xiàn)
#include <stdio.h>
#define OK 1;
#define ERROR 0;
#define TRUE 1;
#define FALSE 0;
#define MAXSIZE 20 /* 定義線性表可能達(dá)到的最大長(zhǎng)度 */
typedef int ElemType;
typedef struct {
ElemType data[MAXSIZE];
int length;
}SqList;
typedef int Status;
// 單鏈表
typedef struct Node{
ElemType data; // 數(shù)據(jù)域
struct Node * next; // 指針域
}Node;
// 取別名
typedef struct Node * LinkList;
/**
* 用快慢指針快速找到未知長(zhǎng)度單鏈表的中間節(jié)點(diǎn)
*/
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;
}
}
// 中間節(jié)點(diǎn)
*e = mid->data;
return OK;
}
