// # -*- coding:utf-8 -*- // # @Author: Mr.chen(ai-chen2050@qq.com) // # @Date: 2018-08-16 16:35:13 // 注：此為第二彈，主要講解鏈表相關面試筆試題，要求手寫 // 注意，在涉及到鏈表的時候，形參傳遞鏈表頭指針過來的時候，如果在函數中需要改變 // 頭結點的指向，則需要傳遞二級指針， **，否則，不能改變其指針的指向#include <iostream> #include <stack>// 節點結構體定義如下： struct ListNode {int m_value;ListNode * m_pNext; };/* 1、向鏈表結尾添加一個節點, 如果該鏈表就是一個空鏈表時，即頭結點就是該值的節點，因此可能改變頭指針故需要傳遞一個 二級指針 */ void AddToTail(ListNode ** pHead,int value) {ListNode * pNew = new ListNode();pNew->m_value = value;pNew->m_pNext = NULL;//判斷傳遞過來的是否是空鏈表if(NULL == *pHead){*pHead = pNew;}else { // 定義一個棧對象指針指向頭指針指向的頭結點ListNode *pNode = *pHead;while(pNode->m_pNext != NULL)pNode = pNode->m_pNext;// 找到鏈表結尾pNode->m_pNext = pNew;} }/* 2、在鏈表中找到第一個含有該值的節點，并且刪除它 */ void RemoveNode(ListNode ** pHead,int value) {if(NULL == pHead || NULL == *pHead)return;ListNode * pDeleted = NULL;if((*pHead)->m_value == value){pDeleted = *pHead;*pHead = (*pHead)->m_pNext;}else {ListNode *pNode = *pHead;while(NULL != pNode->m_pNext && pNode->m_pNext->m_value != value)pNode = pNode->m_pNext;if(NULL != pNode->m_pNext && pNode->m_pNext->m_value == value){pDeleted = pNode->m_pNext;pNode->m_pNext = pNode->m_pNext->m_pNext;}}if(NULL != pDeleted){delete pDeleted;pDeleted = NULL;} }/* 3、輸入一個鏈表的頭結點，從尾到頭打印出每個節點的值，一般會想到如果翻轉鏈表的指向，在打印應該比較簡單，但是打印輸出一般只是只讀屬性，不建議改變原鏈表結構，可考慮棧結構，實現先進后出，或者使用遞歸（遞歸的本質就是棧結構） */// 法一、使用棧結構 void printListReverse(ListNode *pHead) {std::stack<ListNode *> nodes;ListNode * pNode = pHead;while(NULL != pNode){nodes.push(pNode);pNode = pNode->m_pNext;}while(!node.empty()){pNode = node.top();std::cout<< pNode->m_value <<std::endl;node.pop();} }// 法二、使用遞歸 void printListReverse(ListNode *pHead) {if(NULL != pHead){ // 只要沒有到達鏈表的尾部就遞歸調用if(NULL != pHead->m_pNext)printListReverse(pHead->m_pNext);std::cout<< pHead->m_value <<std::endl;} }/* 4、給定單鏈表的頭指針和節點指針，定義一個函數在 O(1) 的時間內刪除該節點。由于是單向鏈表，法一：按常規的思路就是需要先找到刪除節點的前一個節點，然后將前一個節點的pNext指向刪除節點的下一個節點，故需要輪循鏈表，則時間復雜度為 O(n)。法二：不用找到前一個節點，直接將刪除節點的下一個節點的數據賦值給刪除節點，然后將刪除節點的pNext指向原來節點的下兩個節點即可。此外，還需考慮特殊用例，刪除節點為尾節點，然需要遍歷，原鏈表中只有一個節點，即刪除該節點，即為頭結點。需要將指針置為 NULL。時間復雜度為[(n-1)O(1) + O(n)] /n,滿足O(1),但是我們默認該節點一定是在鏈表中的，因為要判斷該節點是否在鏈表中，仍需要O(n)的判斷時間復雜度。（可認為面試官默認了這個前提，也可以向面試官提出來） */ void DeleteNode(ListNode ** pHead,ListNode* pDeleted) {// 有一個指針為 NULL 都返回if(!pHead || !pDeleted)return;// 按照 pDeleted 的情況來分成三種情況// 要刪除的節點不是尾節點if(NULL != pDeleted->m_pNext){ListNode * pNext = pDeleted->m_pNext;pDeleted->m_value = pNext->m_value;pDeleted->m_pNext = pNext->m_pNext;delete pNext;pNext = NULL;}//鏈表只有一個節點，既是頭節點也是尾節點,這里涉及到要改變頭結點的操作，故實參為二級指針 **else if (*pHead == pDeleted){delete pDeleted;pDeleted = NULL;*pHead = NULL;}//鏈表中有多個節點，刪除尾節點else{ListNode * pNode = *pHead// 找到上一個刪除節點的上一個節點while(pDeleted != pNode->m_pNext)pNode = pNode->m_pNext;pNode->m_pNext = NULL;delete pDeleted;pDeleted = NULL;} }/* 5、輸出鏈表中倒數第 K 個節點，默認尾節點即是倒數第一個，此題典型的應該用前后指針來做，它和判斷鏈表是否有環思路類似(兩個指針移動速度不一樣)，但是應該注意的就是代碼的 【魯棒性】，應該考慮各種異常情況，如，傳入的頭指針 pHead 為空，鏈表的節點數小于 k,以及 k 等于 0，等三種異常情況。（a先走 k-1步，然后 a, b一起移動，速度一樣） */ ListNode * FindKthToTail(ListNode *pHead,unsigned int k) {if(NULL == pHead || k == 0) // 異常情況考慮return NULL;ListNode *pa = pHead;ListNode *pb = NULL;for (unsigned int i=0; i < k - 1; ++i){if(NULL != pa->m_pNext) // 異常情況考慮，length < kpa = pa->m_pNext;else return NULL;}pb = pHead;while(NULL != pa->m_pNext){pa = pa->m_pNext;pb = pb->m_pNext;}return pb; }/* 6、翻轉鏈表，強調點【代碼的魯棒性】,與其很快的寫出一個漏洞百出的代碼，不如仔細分析在寫出一個魯棒的代碼。面試者怎么避免錯誤呢，一個很好的辦法就是提前想好測試用例，其實，面試官檢查面試者的代碼也是用他事先準備好了的測試用例，如果我們可以事先想到那么就很好了。一般涉及到鏈表的題，都是想考察面試者的操作指針的能力，在本題目中如果不引入額外的空間復雜度，則直觀的想法就是直接在原鏈上翻轉指向，就會涉及到一個鏈表斷裂的問題，我們把鏈表抽象成前中后三段，只研究其中的任意三個點的時候（如 h,i,j），發現在 while 循環中去改變指向時，為了記住節點狀態，不讓鏈表斷掉，我們至少需要三個指針，分別指向當前的節點以及它前一個節點，以及后一個節點。最后在翻轉之后我們需要返回新的頭結點，其實新的頭結點就是原鏈表的尾節點，即原鏈表中pNext 指向為 NULL的節點。本題的測試用例，可以是如下:* 輸入的鏈表頭指針為 NULL* 輸入的鏈表只有一個節點* 輸入的鏈表有多個節點 */// 法一：迭代法 ListNode *ReverseLinkList(ListNode *pHead) {ListNode *pReverseHead = NULL;ListNode *pNode = pHead;ListNode *pPrev = NULL;while(pNode){ListNode* pNext = pNode->m_pNext;if(NULL == pNext)pReverseHead = pNode;pNode->m_pNext = pPrev;pPrev = pNode; pNode = pNext;}return pReverseHead; } // 此題雖然代碼不長，但是仍需要理清楚其中的邏輯關系// 法二：遞歸（類似棧功能）實現,即就不用循環了 注：在文末可查看圖解。 ListNode *ReverseLinkList(ListNode *pHead) {if(pHead == NULL || pHead->m_pNext == NULL){return pHead; // 若鏈表為空，就直接返回，若 pHead->m_pNext 為 NULL，則為最后一個節點，為遞歸出口,返回一次。}ListNode *pNewHead = ReverseLinkList(pHead->m_pNext); //新頭結點始終指向原鏈尾節點pHead->m_pNext->m_pNext = pHead; // 翻轉鏈表的指向pHead->m_pNext = NULL; // 新的尾節點賦值為 NULLreturn pNewHead; // 返回頭結點 }/* 7、合并兩個遞增排序鏈表，注意一：異常情況（魯棒性）。注意二：想清楚在寫代碼，當我們用兩個指針分別指向原鏈表時，在依次比較誰小，將小的合并到已經合并的鏈上。典型的是一個遞歸的思想。 */ ListNode *Merge(ListNode *pHead1,ListNode *pHead2) {// 異常值檢測if(NULL == pHead1)return pHead2;else if(NULL == pHead2)return pHead1;ListNode *pMergeHead = NULL;// 開始遞歸if(pHead1->m_value < pHead2->m_value){pMergeHead = pHead1;pMergeHead->m_pNext = Merge(pHead1->m_pNext,pHead2);}else {pMergeHead = pHead2;pMergeHead->m_pNext = Merge(pHead1,pHead2->m_pNext);}return pMergeHead; }/* 8、輸入兩個鏈表，找出它們的第一個公共節點，此題有三種思路：法一:蠻力法，輪循鏈表一的每一個節點的時候去輪循另外一個鏈表的每一個節點，比較是否相同，時間復雜度O(mn), 法二：如果倆個鏈表有公共節點，則它的拓撲結構一定是 Y ,故我們換一種思路，從兩個鏈表的最后的節點開始比較，一直到最后一個相同的節點，即為相交節點的入口，但是對于單鏈表，想要找到最后的節點，從后面比較，即后進先比較。故我們可以分別用兩個棧去存儲，故時間復雜度為O(m+n),空間復雜度也為O(m+n)。法三：（也是推薦方法）其實從拓撲關系可知，主要是考慮到兩個鏈長不一樣，不能依次 ++，然后比較。故我們可以采取兩次遍歷的方法，第一次遍歷先計算兩個鏈的長度，如a鏈比b鏈長多少n。第二次遍歷的時候，讓長的先走n步，然后在兩個鏈的指針一起走，找到第一個相同的節點，即為相交的第一個公共節點。時間復雜度為 O(m+n),相比第二個方法沒了空間復雜度。 *///先定義計算鏈長的函數 unsigned int GetListLength(ListNode *pHead) {unsigned int nLength = 0;ListNode * pNode = pHead;while(pNode != NULL){++nLength;pNode = pNode->m_pNext;}return nLength; }ListNode *FindFirstCommonNode(ListNode *pHead1,ListNode *pHead2) {// 獲取鏈表的長度unsigned int nLength1 = GetListLength(pHead1);unsigned int nLength2 = GetListLength(pHead2);// 獲取差值int nLengthDif = nLength1 - nLength2;ListNode *pHeadLenthLong = pHead1;ListNode *pHeadLenthShort = pHead2;if(nLength2 > nLenght1){pHeadLenthLong = pHead2;pHeadLenthShort = pHead1;nLengthDif = nLength2 - nLength1;}// 先在長鏈上先走幾步for(int i=0; i< nLengthDif; i++)pHeadLenthLong = pHeadLenthLong->m_pNext;// 然后一起遍歷while((pHeadLenthLong != NULL) && (pHeadLenthShort != NULL) && (pHeadLenthLong != pHeadLenthShort)){pHeadLenthLong = pHeadLenthLong->m_pNext;pHeadLenthShort = pHeadLenthShort->m_pNext;}// 得到第一個公共節點ListNode *pFirstCommonNode = pHeadLenthLong;return pFirstCommonNode; }/* 9、圓圈中最后剩下的數字（約瑟夫環問題），0,1,····, n-1,這 n 個數字排成一個圓圈，從數字 0 開始每次從圓圈中刪除第 m 個數字，求出這個圓圈里面的最后一個數字。例如：0, 1, 2, 3, 4 這五個數字組成一個圓圈，從 0 開始每次刪除第三個數字，則刪除的前四個數字依次是 2，0, 4，1 。因此，最后剩下的數字是 3。解決這個問題，這里介紹兩種方法，法一：經典的方法，用環形鏈表模擬圓圈，開始游戲。法二：建立數據模型，利用數字規律，用數學的方法去解決它，直接計算出最后剩下的數字。法一：如果面試官允許，可以用標準模板庫 std::list 去模擬，不過，為了讓其具有循環鏈表的特性，需要每次遍歷到尾節點的時候，迭代器回到起始節點（代碼如下）。法二(如下描述使用語言有不當之處，首先 f(m,n) 應該是代表的是一個處理過程，計算機科學是對過程的抽象，其次在尋找遞推公式時，是想讓問題規模變小而需要保持輸入模式一樣，故而尋找了兩個仿射變換，最后找到遞推公式，使用遞歸或迭代都可以實現該算法。)： 首先我們定義一個關于 n和m 方程 f(m,n)，表示在 n 個數字，0,1,····,n-1。每次刪除第 m 個數字最后剩下的數字。在其中，第一個刪除的數字是 （m-1) % n。為了簡單起見，我們把它記為 k,那么刪除第 K 個數字后，剩下的 n-1 個數字為 0,1,····, k-1, k+1, ····, n-1,并且下一次從 k+1 開始計數，相當于形成了如下序列: k+1, ····, n-1, 0,1,····, k-1。該序列最后剩下的序列也是關于 n, m 的函數，但是由于不是從 0,開始故有別于前面的函數模型，我們暫且記為 f'(n-1,m),由題意可知，在一次刪除一個元素后，雖然序列順序變了，但是可以知道， f(m,n) = f'(n-1,m)。 接下來，我們對剩下的序列做一個仿射映射（或者說平移映射）即：k+1 --> 0 , k+2 --> 1, ···, k-1 --> n-2。定義映射函數p, p = (x-k-1) % n,其中x是映射前，ｐ為映射后。它的逆映射為　ｐ'(x) = ( x+k+1 )% n, 映射之后我們可以發現它與最開始我們建立的模型，序列一致了,故可以用 f 函數來表示，故映射之前序列中剩下的數字 f'(n-1,m) = p'[f(n-1,m)] = [f(n-1,m) + k +1]% n ,帶入K = (m -1)%n ,可得 f(n,m) = f'(n-1,m) = [f(n-1,m) + m]% n, 邊界，當n = 1時，只有 0 故最后剩下的只有 0，我們把這種關系表示為 f(n,m) = 0, n=1. f(n,m) = [f(n-1,m) + m]% n, n>1,于是，我們就可以用遞歸或者循環來實現了，時間復雜度為O(n),空間復雜度為 O(1).循環鏈表的應用，重點考察抽象建模的能力（建立數學模型，然后嘗試用經典的編程思想和數學方法去解決它）。 */// 法一：循環鏈表 int LastRemain(unsigned int n,unsigned int m) {if( n< 1 || m < 1)return -1;unsigned int i = 0;//定義鏈表std::list<int> numbers;for (i = 0; i< n; ++i)numbers.push_back(n);list<int>::iterator current = numbers.begin();while(numbers.size() > 1){// 找到 m 的位置for(int i = 1; i<m; ++i){current ++; // 注意迭代器是可以直接 ++ 的，因為重載了 ++ 運算符if(current == numbers.end())current = numbers.begin();}list<int>::iterator next = ++ current;if(next == numbers.end())next = numbers.begin()-- current;numbers.erase(current);current = next;}return *(current); } //每刪除一個數字，需要 m步計算，共 n 個數字，故總的時間復雜度為O(mn),空間復雜度為O(n)// 法二：抽象 + 建模 用數學方法解答（原理基于上面解答） int LastRemaining(unsigned int n,unsigned int m) {if(n<1 || m<1)return -1;// 邊界 n = 1時，最后為 0int last = 0;for(int i=2; i<=n ;i++){last = (last + m) % i;}return last; }/* 10、二叉搜索樹和雙向鏈表，要求：輸入二叉搜索樹，將二叉搜索樹轉換成排序的雙向鏈表。要求不能創建新的節點，只能調整樹中節點指針的指向，比如：如下圖中所示，輸出排序后的雙向鏈表。二叉搜索樹也是一種排序的數據結構，并且每個節點也有兩個指向子節點的指針，故理論上是可以進行相互轉換的，在二叉搜索樹中，左子節點的值小于父節點，右子節點的值大于父節點，故我們可以將指向左子節點的指針改為指向前一個節點的指針，將指向右子節點的指針改為指向后一個節點的指針。具體方法如下：由于中序遍歷二叉搜索樹，得到的便是一個排好序的序列，故當我們遍歷到根節點的時候，需要將其看成三個部分，對于圖中的值為 10 的根節點，根節點為 6 的左子樹，根節點為 14 的右子樹，由排序鏈表的定義，節點10 將會和左子樹中最大的一個節點（8）鏈接，和右子樹中最小的一個節點（12）鏈接，按照中序遍歷的特點，當我們遍歷到根節點時，它的左子樹已經轉換成了一個排序的鏈表，并且最后一個節點是當前最大節點，此時我們只需要將根節點鏈接到該有序鏈表的后面，并且將尾指針指向新的尾節點，在鏈接上右子樹已經排好序的有序鏈表，即可完成轉換。至于左右子樹怎么轉換，我們可以很容易的想到遞歸的思想。 */

?

// 二叉節點樹的節點定義如下： struct BiTreeNode {int m_value;BiTreeNode* m_pLeft;BiTreeNode* m_pRight; };BiTreeNode* Convert(BiTreeNode* pRootofTree) {BiTreeNode* pLastNodeInList = NULL;//開始轉換ConvertNode(pRootofTree,&pLastNodeInList);// pLastNodeInList 指向雙向鏈表的最后一個節點，但我們需要返回頭結點BiTreeNode* pHeadofTree = pLastNodeInList;while(pHeadofTree != NULL && pHeadofTree->m_pLeft != NULL)pHeadofTree = pHeadofTree->m_pLeft;//返回頭節點return pHeadofTree; }void ConvertNode(BiTreeNode* pNode,BiTreeNode** pLastNodeInList) {if(NULL == pNode)return;BiTreeNode* pCurrent = pNode;// 找到最左邊的節點if(pCurrent->m_pLeft != NULL)ConvertNode(pCurrent->m_pLeft,pLastNodeInList);//改變左指向,如果尾節點不為 NULL，增加右指向，最后更新尾指針指向pCurrent->m_pLeft = *pLastNodeInList;if(*pLastNodeInList != NULL)(*pLastNodeInList)->m_pRight = pCurrent;*pLastNodeInList = pCurrent; // 注意，這里要改變pLastNodeInList 的指向由于是二級指針，故需要解引用 *// 判斷是否有右子樹if(pCurrent->m_pRight != NULL)ConvertNode(pCurrent->m_pRight ,pLastNodeInList); }

?

總結

以上是生活随笔為你收集整理的面试基础算法及编程 第二弹（链表相关：主要考察指针的应用）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。