1.求鏈表節(jié)點(diǎn)

while遍歷node->next，然后node賦值node->next

unsigned int GetListLength(ListNode * pHead)
{
    if(pHead == NULL)
        return 0;
 
    unsigned int nLength = 0;
    ListNode * pCurrent = pHead;
    while(pCurrent != NULL)
    {
        nLength++;
        pCurrent = pCurrent->m_pNext;
    }
    return nLength;
}

2.反向單鏈表

創(chuàng)建兩個(gè)變量，一個(gè)表示當(dāng)前列表節(jié)點(diǎn)，一個(gè)表示新列表節(jié)點(diǎn)。舊列表的下一個(gè)節(jié)點(diǎn)設(shè)置為設(shè)置為新列表的節(jié)點(diǎn)，舊列表當(dāng)前節(jié)點(diǎn)當(dāng)做新節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。

ListNode * ReverseList(ListNode * pHead)
{
        // 如果鏈表為空或只有一個(gè)結(jié)點(diǎn)，無(wú)需反轉(zhuǎn)，直接返回原鏈表頭指針
    if(pHead == NULL || pHead->m_pNext == NULL)  
        return pHead;
 
    ListNode * pReversedHead = NULL; // 反轉(zhuǎn)后的新鏈表頭指針，初始為NULL
    ListNode * pCurrent = pHead;
    while(pCurrent != NULL)
    {
        ListNode * pTemp = pCurrent;
        pCurrent = pCurrent->m_pNext;
        pTemp->m_pNext = pReversedHead; // 將當(dāng)前結(jié)點(diǎn)摘下，插入新鏈表的最前端
        pReversedHead = pTemp;
    }
    return pReversedHead;
}

3.鏈表查詢(xún)倒數(shù)第k個(gè)節(jié)點(diǎn)

設(shè)置兩個(gè)指針，前者不動(dòng)，后者做next賦值k次，然后開(kāi)始一起執(zhí)行賦值next，后一個(gè)為null時(shí)，取前一個(gè)節(jié)點(diǎn)

4.鏈表查詢(xún)中間節(jié)點(diǎn)

兩個(gè)指針，一個(gè)是另一個(gè)的賦值的兩倍。

5.從尾到頭打印單鏈表

使用數(shù)組保存。將next節(jié)點(diǎn)插入到第一個(gè)位置。

6.已知兩個(gè)單鏈表pHead1 和pHead2 各自有序，把它們合并成一個(gè)鏈表依然有序

依次判斷鏈表1的某個(gè)位置節(jié)點(diǎn)是否小于另一個(gè)位置的節(jié)點(diǎn)，分別做計(jì)算。

ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)
{
    if(pHead1 == NULL)
        return pHead2;
    if(pHead2 == NULL)
        return pHead1;
    ListNode * pHeadMerged = NULL;
    if(pHead1->m_nKey < pHead2->m_nKey)
    {
        pHeadMerged = pHead1;
        pHeadMerged->m_pNext = MergeSortedList(pHead1->m_pNext, pHead2);
    }
    else
    {
        pHeadMerged = pHead2;
        pHeadMerged->m_pNext = MergeSortedList(pHead1, pHead2->m_pNext);
    }
    return pHeadMerged;
}

7.判斷一個(gè)單鏈表中是否有環(huán)

兩個(gè)指針一個(gè)是另一個(gè)兩倍。如果直到結(jié)束都沒(méi)有相等的則沒(méi)有環(huán)。

bool HasCircle(ListNode * pHead)
{
    ListNode * pFast = pHead; // 快指針每次前進(jìn)兩步
    ListNode * pSlow = pHead; // 慢指針每次前進(jìn)一步
    while(pFast != NULL && pFast->m_pNext != NULL)
    {
        pFast = pFast->m_pNext->m_pNext;
        pSlow = pSlow->m_pNext;
        if(pSlow == pFast) // 相遇，存在環(huán)
            return true;
    }
    return false;
}

8.判斷兩個(gè)單鏈表是否相交

對(duì)第一個(gè)鏈表遍歷，計(jì)算長(zhǎng)度len1，同時(shí)保存最后一個(gè)節(jié)點(diǎn)的地址。
對(duì)第二個(gè)鏈表遍歷，計(jì)算長(zhǎng)度len2，同時(shí)檢查最后一個(gè)節(jié)點(diǎn)是否和第一個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)相同，若不相同，不相交，結(jié)束。
兩個(gè)鏈表均從頭節(jié)點(diǎn)開(kāi)始，假設(shè)len1大于len2，那么將第一個(gè)鏈表先遍歷len1-len2個(gè)節(jié)點(diǎn)，此時(shí)兩個(gè)鏈表當(dāng)前節(jié)點(diǎn)到第一個(gè)相交節(jié)點(diǎn)的距離就相等了，然后一起向后遍歷，知道兩個(gè)節(jié)點(diǎn)的地址相同。
時(shí)間復(fù)雜度，O(len1+len2)。參考代碼如下：

bool IsIntersected(ListNode * pHead1, ListNode * pHead2)
{
        if(pHead1 == NULL || pHead2 == NULL)
                return false;
 
    ListNode * pTail1 = pHead1;
    while(pTail1->m_pNext != NULL)
        pTail1 = pTail1->m_pNext;
 
    ListNode * pTail2 = pHead2;
    while(pTail2->m_pNext != NULL)
        pTail2 = pTail2->m_pNext;
    return pTail1 == pTail2;

9.兩個(gè)節(jié)點(diǎn)相交的第一個(gè)節(jié)點(diǎn)

先判斷兩個(gè)鏈表是否有交點(diǎn)。然后將長(zhǎng)的節(jié)點(diǎn)移到跟短的鏈表一樣的位置，然后一起移動(dòng)，直到兩個(gè)節(jié)點(diǎn)一樣。

ListNode* GetFirstCommonNode(ListNode * pHead1, ListNode * pHead2)
{
    if(pHead1 == NULL || pHead2 == NULL)
        return NULL;
 
    int len1 = 1;
    ListNode * pTail1 = pHead1;
    while(pTail1->m_pNext != NULL)
    {
        pTail1 = pTail1->m_pNext;
        len1++;
    }
 
    int len2 = 1;
    ListNode * pTail2 = pHead2;
    while(pTail2->m_pNext != NULL)
    {
        pTail2 = pTail2->m_pNext;
        len2++;
    }
 
    if(pTail1 != pTail2) // 不相交直接返回NULL
        return NULL;
 
    ListNode * pNode1 = pHead1;
    ListNode * pNode2 = pHead2;
        // 先對(duì)齊兩個(gè)鏈表的當(dāng)前結(jié)點(diǎn)，使之到尾節(jié)點(diǎn)的距離相等
    if(len1 > len2)
    {
        int k = len1 - len2;
        while(k--)
            pNode1 = pNode1->m_pNext;
    }
    else
    {
        int k = len2 - len1;
        while(k--)
            pNode2 = pNode2->m_pNext;
    }
    while(pNode1 != pNode2)
    {
        pNode1 = pNode1->m_pNext;
        pNode2 = pNode2->m_pNext;
    }
        return pNode1;
}

10.已知一個(gè)單鏈表中存在環(huán)，求進(jìn)入環(huán)中的第一個(gè)節(jié)點(diǎn)

首先判斷是否存在環(huán)，若不存在結(jié)束。在環(huán)中的一個(gè)節(jié)點(diǎn)處斷開(kāi)（當(dāng)然函數(shù)結(jié)束時(shí)不能破壞原鏈表），這樣就形成了兩個(gè)相交的單鏈表，求進(jìn)入環(huán)中的第一個(gè)節(jié)點(diǎn)也就轉(zhuǎn)換成了求兩個(gè)單鏈表相交的第一個(gè)節(jié)點(diǎn)。參考代碼如下：

ListNode* GetFirstNodeInCircle(ListNode * pHead)
{
    if(pHead == NULL || pHead->m_pNext == NULL)
        return NULL;
 
    ListNode * pFast = pHead;
    ListNode * pSlow = pHead;
    while(pFast != NULL && pFast->m_pNext != NULL)
    {
        pSlow = pSlow->m_pNext;
        pFast = pFast->m_pNext->m_pNext;
        if(pSlow == pFast)
            break;
    }
    if(pFast == NULL || pFast->m_pNext == NULL)
        return NULL;
 
    // 將環(huán)中的此節(jié)點(diǎn)作為假設(shè)的尾節(jié)點(diǎn)，將它變成兩個(gè)單鏈表相交問(wèn)題
    ListNode * pAssumedTail = pSlow; 
    ListNode * pHead1 = pHead;
    ListNode * pHead2 = pAssumedTail->m_pNext;
 
    ListNode * pNode1, * pNode2;
    int len1 = 1;
    ListNode * pNode1 = pHead1;
    while(pNode1 != pAssumedTail)
    {
        pNode1 = pNode1->m_pNext;
        len1++;
    }
    
    int len2 = 1;
    ListNode * pNode2 = pHead2;
    while(pNode2 != pAssumedTail)
    {
        pNode2 = pNode2->m_pNext;
        len2++;
    }
 
    pNode1 = pHead1;
    pNode2 = pHead2;
    // 先對(duì)齊兩個(gè)鏈表的當(dāng)前結(jié)點(diǎn)，使之到尾節(jié)點(diǎn)的距離相等
    if(len1 > len2)
    {
        int k = len1 - len2;
        while(k--)
            pNode1 = pNode1->m_pNext;
    }
    else
    {
        int k = len2 - len1;
        while(k--)
            pNode2 = pNode2->m_pNext;
    }
    while(pNode1 != pNode2)
    {
        pNode1 = pNode1->m_pNext;
        pNode2 = pNode2->m_pNext;
    }
    return pNode1;

}

11.給出一單鏈表頭指針pHead和一節(jié)點(diǎn)指針pToBeDeleted，O(1)時(shí)間復(fù)雜度刪除節(jié)點(diǎn)pToBeDeleted

對(duì)于刪除節(jié)點(diǎn)，我們普通的思路就是讓該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)指向該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，這種情況需要遍歷找到該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(n)。對(duì)于鏈表，鏈表中的每個(gè)節(jié)點(diǎn)結(jié)構(gòu)都是一樣的，所以我們可以把該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的數(shù)據(jù)復(fù)制到該節(jié)點(diǎn)，然后刪除下一個(gè)節(jié)點(diǎn)即可。要注意最后一個(gè)節(jié)點(diǎn)的情況，這個(gè)時(shí)候只能用常見(jiàn)的方法來(lái)操作，先找到前一個(gè)節(jié)點(diǎn)，但總體的平均時(shí)間復(fù)雜度還是O(1)。

void Delete(ListNode * pHead, ListNode * pToBeDeleted)
{
    if(pToBeDeleted == NULL)
        return;
    if(pToBeDeleted->m_pNext != NULL)
    {
        pToBeDeleted->m_nKey = pToBeDeleted->m_pNext->m_nKey; // 將下一個(gè)節(jié)點(diǎn)的數(shù)據(jù)復(fù)制到本節(jié)點(diǎn)，然后刪除下一個(gè)節(jié)點(diǎn)
        ListNode * temp = pToBeDeleted->m_pNext;
        pToBeDeleted->m_pNext = pToBeDeleted->m_pNext->m_pNext;
        delete temp;
    }
    else // 要?jiǎng)h除的是最后一個(gè)節(jié)點(diǎn)
    {
        if(pHead == pToBeDeleted) // 鏈表中只有一個(gè)節(jié)點(diǎn)的情況
        {
            pHead = NULL;
            delete pToBeDeleted;
        }
        else
        {
            ListNode * pNode = pHead;
            while(pNode->m_pNext != pToBeDeleted) // 找到倒數(shù)第二個(gè)節(jié)點(diǎn)
                pNode = pNode->m_pNext;
            pNode->m_pNext = NULL;
            delete pToBeDeleted;
        }   
    }
}