面試題一般會(huì)有普通方法和高級(jí)方法，高級(jí)方法無疑會(huì)大大的加分！

題目一：快速找到未知長度單鏈表的中間節(jié)點(diǎn)（騰訊面試題）

普通解法

• 思路
  首先遍歷一遍單鏈表以確定單鏈表的長度。然后再次從頭結(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á)到的最大長度 */

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;

/**
 * 用快慢指針快速找到未知長度單鏈表的中間節(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;
}