本來以為一篇就能寫完的眯娱，后來又感覺一篇多了一些驶乾，所以關于鏈表的簡單算法題有加了個續(xù)篇惰爬，和上一篇一樣，難度不會太大辜王。

• 鏈表中倒數(shù)第k個結點
• 合并兩個排序的鏈表
• 找到兩個鏈表中的第一個公共結點

1.鏈表中的倒數(shù)第k個結點

問題描述：輸入一個鏈表劈狐，計算鏈表中的倒數(shù)第k個結點(從1開始計數(shù))。

算法思想

我們可以分析鏈表結點個數(shù)n和倒數(shù)第k個結點之間的關系呐馆，如果鏈表有n個結點肥缔，那么它的倒數(shù)第k個結點也就是鏈表順著數(shù)的第n-k+1個結點。
思路一：先遍歷鏈表汹来，得到結點個數(shù)n续膳，再遍歷鏈表，找到第n-k+1個結點收班。這一種思路需要兩次遍歷鏈表坟岔，時間復雜度為O(n)。
思路二：能不能一次遍歷就找到結點呢摔桦？這就是接下來要說的了社付。我們可以使用兩個指針，第一個指針從頭結點開始邻耕，向前走k-1步瘦穆，然后第二個指針指向首結點，接下來兩個指針順序后移赊豌，當?shù)谝粋€指針指向最后一個結點的時候扛或，第二個指針剛好指向倒數(shù)第k個幾點。兩個指針之間間隔為k-1碘饼。

代碼：

算法思想清楚了之后熙兔，代碼就簡單多了悲伶。寫出代碼之后，我們需要關注其魯棒性住涉，針對特殊的輸入麸锉，代碼能否完成任務。這些都是代碼中需要考慮到的舆声。
特殊輸入：
1.如果pHead為NULL花沉，那么不存在倒數(shù)第K個結點，應該返回NULL媳握。
2.k接收的無符號數(shù)碱屁，如果輸入k=0,因為k是無符號數(shù)，for循環(huán)k-1次的時候,得到的將不會是-1蛾找，而是一個非常大的數(shù)字娩脾，for循環(huán)的次數(shù)會超過我們的預期。
3.如果輸入的k大于鏈表結點總數(shù)打毛，那么在for循環(huán)遍歷鏈表的時候柿赊，會出現(xiàn)指向NULL的指針。

鏈表的數(shù)據結構定義：

typedef struct ListNode *list_pointer;
typedef struct ListNode
{
    int value;
    list_pointer link;
};
list_pointer pHead;

查找鏈表中的倒數(shù)第k個結點（從1開始計數(shù)）幻枉。

list_pointer FindKthNodeFromEnd(list_pointer pHead, unsigned int k)
{
    //鏈表中的結點計數(shù)從1開始碰声，所以不存在倒數(shù)第0個結點
    if (pHead == NULL || k == 0) {
        return NULL;
    }
    list_pointer pAhead = pHead;
    list_pointer pBehind;

    for (int i = 0; i < k - 1; i++)
    {
        if (pAhead->link)//防止k大于鏈表結點個數(shù)的情況發(fā)生
        {
            pAhead = pAhead->link;
        }
        else
        {
            fprintf(stderr, "K is bigger than length of linklist\n");
            exit(1);
        }
    }

    pBehind = pHead;
    while (pAhead->link)//判斷pAhead是不是指向最后一個結點
    {
        pAhead = pAhead->link;
        pBehind = pBehind->link;
    }
    return pBehind;
}

相關題目

類似的題目還有很多，我們可以借助兩個指針熬甫，很快的得到結果奥邮。
題目一：求鏈表的中間結點，如果鏈表結點數(shù)為奇數(shù)罗珍，則輸出中間結點洽腺，如果鏈表結點數(shù)為偶數(shù)， 則輸出中間兩個中的一個覆旱。
算法思想：定義兩個指針蘸朋，一個指針一次走一步，另一個指針一次走兩步扣唱，當走得快的指針到達鏈表尾是藕坯，走得慢的剛好指向鏈表中間結點。
題目二：判斷一個單向鏈表是否是環(huán)形鏈表噪沙。
算法思想：定義兩個指針炼彪，從首結點開始，一個指針一次走一步正歼，另一個指針一次走兩步辐马，如果走的快的指針追到了走得慢的指針，那么這個鏈表就是環(huán)形的局义，如果走的快的指針走到了鏈表的末尾都沒有追到慢的指針喜爷，那么就不是環(huán)形鏈表冗疮。

代碼

這里寫了題目一的代碼，可以參考一下檩帐。需要注意的代碼中的while的循環(huán)條件术幔，判斷了pAhead和pAhead->link，這里是判斷是否指向了尾節(jié)點湃密，如果鏈表結點數(shù)為偶數(shù)诅挑，是用pAhead==NULL來判斷是否到尾節(jié)點的；如果鏈表有奇數(shù)個結點泛源，就是用pAhead->link==NULL來判斷的拔妥。

//找中間結點
list_pointer getTheMiddleNode(list_pointer pHead)
{
    if (pHead == NULL){
        fprintf(stderr, "the linklist is empty.\n" );
        exit(1);
    }
    if (pHead->link == NULL)//如果鏈表中只有一個結點，那么中間結點就是該結點
        return pHead;
    list_pointer pAhead = pHead, pBehind = pHead;
    //如果走的快的指針沒有指向尾結點
    while (pAhead && pAhead->link)
    {
        pAhead = pAhead->link->link;
        pBehind = pBehind->link;
    }
    return pBehind;
}

2.合并兩個排序的鏈表

問題描述：輸入兩個排好序的鏈表俩由，合并兩個鏈表毒嫡，并返回合并后的鏈表的頭結點癌蚁。

算法思想

用兩個指針幻梯，一個指向a鏈表的結點，一個指向b鏈表的結點努释。都從鏈表頭開始碘梢，依次比較。針對兩個鏈表中的第一個結點伐蒂，比較大小煞躬，小的結點加到合并的之后的鏈表中，然后加入合并鏈表的那個鏈表指針后移逸邦，然后計算省下結點的的頭結點恩沛，接下來將計算出來的結點接到合并鏈表的鏈表尾，剩余的結點也是這樣處理缕减。這樣分析下來雷客，就是典型的遞歸了。使用遞歸桥狡，我們可以很快的解決這道題搅裙。

代碼

//合并兩個排好序的鏈表,用遞歸，每次都比較鏈表中剩余結點的頭結點
list_pointer Merge(list_pointer pHead1, list_pointer pHead2)
{
    if (pHead1 == NULL)
        return pHead2;
    if (pHead2 == NULL)
        return pHead1;

    list_pointer pMerge = NULL;//合并之后的鏈表的頭結點
    //每次都比較鏈表中剩余結點的頭指針
    if (pHead1->value < pHead2->value)
    {
        pMerge = pHead1;
        pMerge->link = Merge(pHead1->link, pHead2);
    }
    else
    {
        pMerge = pHead2;
        pMerge->link = Merge(pHead1, pHead2->link);//接到上一個結點后面
    }
    return pMerge;
}

3.找到兩個鏈表中的第一個公共結點

問題描述：輸入兩個鏈表裹芝，計算兩個鏈表的公共結點部逮。

算法思想

思路一：蠻力法，遍歷第一個鏈表嫂易，每遍歷一個結點時兄朋，在第二個鏈表上順序遍歷所有結點，如果第二個鏈表上有結點和第一個鏈表的結點相等怜械，那么就找到了公共結點蜈漓。這種思路的時間復雜度是O(n^2)穆桂，效率很低。
思路二：首先分析有公共結點的兩個鏈表的特點融虽，如果兩個鏈表存在公共結點享完，那么兩個鏈表都一定存在一個結點，它的link指向相同有额。單向鏈表的每個結點只能有一個指向般又，所以從第一個公共結點開始，之后它們的所有結點都是重合的巍佑，不可能再分叉茴迁。所以兩個有公共結點而部分重合的鏈表，看起來像Y萤衰。

首先堕义，可以確定，如果兩個鏈表有公共結點脆栋，那么公共結點一定是在鏈表尾部倦卖。如果從兩個鏈表的最后一個結點開始比較，遇到最后一個相等的結點就是它們的公共結點了椿争。但是鏈表要定位到最后一個結點就需要從頭遍歷怕膛，最先遍歷到的結點最后比較，最后遍歷到的結點(尾結點)第一個比較秦踪，所以我們可以使用棧褐捻。先遍歷兩個鏈表，用兩個棧來存儲每個結點椅邓。每次比較棧頂結點柠逞，直到比較到最后一個相等的結點。時間復雜度O(m+m)景馁，m,n分別是兩個鏈表的長度板壮，空間復雜度也是O(m+n)。

思路三：用棧的目的就是定位到最后一個元素裁僧，方便從后往前遍歷个束。這樣就解決了兩個鏈表的結點數(shù)不一致時，到達尾結點的時間不同聊疲。換一種思路茬底。如果提前知道鏈表長度，我們就可以知道長的鏈表比短的鏈表多幾個元素获洲，那么長的鏈表先走幾步阱表，然后兩個鏈表開始同時向后遍歷，遇到的第一個相同的結點就是其公共結點了。這種思想的時間復雜度是O(m+n)最爬，但是我們不再需要額外的空間輔助了涉馁。

代碼

思路三代碼。

//計算鏈表長度
unsigned int getLength(list_pointer p)
{
    list_pointer pNode = p;
    int length = 0;
    while (pNode)
    {
        length++;
        pNode = pNode->link;
    }
    return length;
}

//計算兩個鏈表的第一個公共結點
ListNode* FindFirstCommonNode(list_pointer pHead1, list_pointer pHead2)
{
    if (!pHead1 || !pHead2)
        return NULL;
    //得到兩個鏈表的長度
    unsigned int nLength1 = getLength(pHead1);
    unsigned int nLength2 = getLength(pHead2);

    int nLengthDif = nLength1 - nLength2;
    list_pointer pListHeadLong = pHead1;
    list_pointer pListHeadShort = pHead2;

    if (nLength1 < nLength2)
    {
        nLengthDif = nLength2 - nLength1;
        pListHeadLong = pHead2;
        pListHeadShort = pHead1;
    }

    //長的鏈表先走
    for (int i = 0; i < nLengthDif; i++)
    {
        pListHeadLong = pListHeadLong->link;
    }

    while (pListHeadLong && pListHeadShort
        && pListHeadLong != pListHeadShort)
    {
        pListHeadLong = pListHeadLong->link;
        pListHeadShort = pListHeadShort->link;
    }
    //得到第一個公共結點
    ListNode *theCommonNode = pListHeadLong;
    return theCommonNode;
}

總結

遇到這些問題的時候爱致，常規(guī)思路的解決方法我們的通常都能想到烤送，但是時空效率很低，看到這些高效的解決方法的時候糠悯，我覺得真是很奇妙帮坚，快捷方便的解決了問題。我們可以從這些方法之中學習一種思路互艾，比如說一個指針解決不了的试和，試試兩個指針，總結要解決的問題和鏈表特有的存儲結構的關系等纫普。這次就到這里了阅悍，不足之處，請多指教~