舉例：原來(lái)鏈表為1->2->3->4->5翻轉(zhuǎn)為5->4->3->2->1

鏈表結(jié)點(diǎn)定義如下：

struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};

答：

#include "stdafx.h"
#include <iostream>
#include <fstream>

using namespace std;

struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};

//構(gòu)造鏈表
void CreateList(ListNode *&pHead)
{
    fstream fin("list.txt");
    ListNode *pNode = NULL;
    ListNode *pTmp = NULL;
    int data;
    fin>>data;
    while (data)
    {
        pNode = new ListNode;
        pNode->m_nKey = data;
        pNode->m_pNext = NULL;
        if (NULL == pHead)
        {
            pHead = pNode;
            pTmp = pNode;
        }
        else
        {
            pTmp->m_pNext = pNode;
            pTmp = pNode;
        }

        fin>>data;
    }
}

//翻轉(zhuǎn)單鏈表
void ReverseLink(ListNode *&pHead)
{
    if (NULL == pHead)
    {
        return;
    }
    ListNode *pNode = pHead;
    ListNode *Prev = NULL;
    ListNode *pNext = NULL;
    while (NULL != pNode)
    {
        pNext = pNode->m_pNext;
        if (NULL == pNext)
        {
            pHead = pNode;
        }
        pNode->m_pNext = Prev;
        Prev = pNode;
        pNode = pNext;
    }
}

void PrintList(ListNode *pHead)
{
    if (NULL == pHead)
    {
        return;
    }
    ListNode *pNode = pHead;
    while (NULL != pNode)
    {
        cout<<pNode->m_nKey<<"  ";
        pNode = pNode->m_pNext;
    }
    cout<<endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
    ListNode *pHead = NULL;
    cout<<"原來(lái)的鏈表：";
    CreateList(pHead);
    PrintList(pHead);
    ReverseLink(pHead);
    cout<<"翻轉(zhuǎn)的鏈表：";
    PrintList(pHead);

    return 0;
}

運(yùn)行界面如下：

建造鏈表的list.txt文件如下：

12 11 10 9 8 7 6 5 4 3 2 1 0

　　第5題，我也是想錯(cuò)了方向，由于沒(méi)有時(shí)間了，代碼我沒(méi)寫，我只寫了個(gè)思路：即從A點(diǎn)開(kāi)始用廣度優(yōu)先搜索，第一個(gè)到達(dá)B點(diǎn)的肯定是最短路徑，記下此時(shí)A點(diǎn)到B點(diǎn)的步數(shù)，然后統(tǒng)計(jì)從A到B點(diǎn)等于這個(gè)步數(shù)的個(gè)數(shù)。其實(shí)，廣度優(yōu)先搜索只能求出最短路徑，但不能求出所有的最短路徑個(gè)數(shù)，要想求出所有最短路徑的個(gè)數(shù)，要用回溯法(后面我會(huì)給出代碼)。想想當(dāng)時(shí)面試的時(shí)候還振振有詞的向面試官A講解我的思路，也不知道面試官A是怎么想的，也不指出我的錯(cuò)誤，怕是怕我難堪吧。

　　面試官A面完之后已經(jīng)是12點(diǎn)多了，這是又來(lái)了一個(gè)27、8歲的大哥(暫且稱為面試官B)來(lái)面試我，一上來(lái)就給我一道編程題，實(shí)現(xiàn)大數(shù)相加，給出代碼。我又刷刷的寫了20多分鐘，認(rèn)為沒(méi)問(wèn)題了，就拿給面試官B看，看了一小會(huì)，就指出我的代碼錯(cuò)在什么地方了，(哎，畢竟是手寫代碼，錯(cuò)誤肯定很多)，要我改正，一步一步的引導(dǎo)我將我的代碼改正，非常和藹的一位大哥哥，也是和我聊的最久的，聊到了下午2點(diǎn)多，差不多兩個(gè)鐘頭，期間主要問(wèn)的問(wèn)題各種各樣都有：

　　1、技術(shù)相關(guān)：map的實(shí)現(xiàn)機(jī)制是怎么樣的??；模板類的偏特化；動(dòng)態(tài)加載dll和靜態(tài)加載dll的區(qū)別；線程和進(jìn)程的區(qū)別；TCP的四次揮手協(xié)議；給定兩個(gè)數(shù)組a和b，求所有在a數(shù)組中不在b數(shù)組的元素；快速排序的平均時(shí)間復(fù)雜度是多少，證明它的平均時(shí)間復(fù)雜度等。這些問(wèn)題我都一一說(shuō)出了我的答案，主要是我看過(guò)一點(diǎn)<stl源碼剖析>、<算法導(dǎo)論>，所以沒(méi)覺(jué)的有什么難度，好像他也覺(jué)得我回答的還不錯(cuò)。

　　2、其他：3點(diǎn)一刻，求此時(shí)時(shí)針和分針夾角的度數(shù)；對(duì)騰訊這個(gè)公司怎么看；為什么離職；個(gè)人規(guī)劃等。

　　面試官B面完之后，叫我先出去吃午飯，下午回來(lái)還有一次面試。吃飯歸來(lái)之后，又來(lái)了一位也是27、8歲的大哥(暫且稱為面試官C)，給我?guī)椎肋壿嬵}，要我20分鐘寫出答案，在我和他講解我的邏輯題之后，他問(wèn)了幾個(gè)我不熟悉的或者已經(jīng)記不清答案的問(wèn)題：一個(gè)進(jìn)程由哪些方面構(gòu)成，我記得<windows核心編程>一書上有講，但我記不清了，吱吱嗚嗚也沒(méi)說(shuō)出一個(gè)所以然來(lái)，之后又問(wèn)了一個(gè)我不懂怎樣回答的問(wèn)題：你認(rèn)為你的優(yōu)勢(shì)是什么？作為一個(gè)二流學(xué)校畢業(yè)的屌絲，工作還不到2年，沒(méi)學(xué)歷，項(xiàng)目經(jīng)驗(yàn)又沒(méi)什么亮點(diǎn)。實(shí)在不懂怎么說(shuō)，憋了半天只說(shuō)出一句：我基礎(chǔ)還行。之后就沒(méi)在問(wèn)問(wèn)題了，最后面試官B通知我可以回去了。哎，這可能就是導(dǎo)致我最后悲劇的原因吧。

總結(jié)：

　　1、沒(méi)有大公司面試經(jīng)驗(yàn)，并且由于事先也完全沒(méi)有做準(zhǔn)備，好像趕鴨子上架

　　2、基礎(chǔ)一定要扎實(shí)，C++，數(shù)據(jù)結(jié)構(gòu)和算法，操作系統(tǒng)，網(wǎng)絡(luò)編程要熟悉。

　　3、對(duì)自己寫的代碼負(fù)責(zé)

　　4、騰訊的員工非常友好

近期目標(biāo)：

　　1、看數(shù)據(jù)結(jié)構(gòu)和算法

　　2、熟悉C++編程規(guī)范。

　　3、多看別人寫的優(yōu)秀源碼，爭(zhēng)取自己寫的代碼簡(jiǎn)潔易懂

最后：

　　給出筆試的最后一道編程題的題目和我寫的答案，如果有任何問(wèn)題，請(qǐng)指正。

　　題目：給定一個(gè)8*8的方格子，如下圖所示，求A點(diǎn)到B點(diǎn)的最短路徑有多少條？用算法實(shí)現(xiàn)。

　　答：從圖中可以看出，A點(diǎn)到B點(diǎn)的最短路徑為16，即A點(diǎn)橫走8小格，縱走8小格才能最快到達(dá)B點(diǎn)，這是排列組合的問(wèn)題，即從最短路徑16中選取8個(gè)橫走的小格子(或者從最短路徑16中選取8個(gè)縱走的小格子)。所以從A點(diǎn)到B點(diǎn)的最短路徑條數(shù)，直接可以算出來(lái)，即為：

　　代碼如下：

size_t g_num = 0;  //統(tǒng)計(jì)A點(diǎn)到B點(diǎn)的最短路徑條數(shù)

void shortestPathNumber(char grid[9][9], int row, int col, int &step)
{
if (row < 0 || row > 8 || col < 0 || col > 8 || grid[row][col] == '*' || step > 16)
    {
return;
    }
if (row == 0 && col == 8) 
    {
if (step == 16)  //已到達(dá)B點(diǎn)，且等于最短路徑16，就累加
        {
            g_num++;
        }
    }
else
    {
        grid[row][col] = '*'; //標(biāo)記該點(diǎn)已訪問(wèn)
        step++;

        shortestPathNumber(grid, row, col + 1, step);
        shortestPathNumber(grid, row + 1, col, step);
        shortestPathNumber(grid, row, col - 1, step);
        shortestPathNumber(grid, row - 1, col, step);

        grid[row][col] = '.'; //回溯
        step--;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
char grid[9][9] = {0};
int step = 0;
    shortestPathNumber(grid, 8, 0, step); //從A點(diǎn)開(kāi)始搜索
    cout<<"A點(diǎn)到B點(diǎn)的最短路徑條數(shù)為: "<<g_num<<endl;

return 0;
}

運(yùn)行界面如下：