鏈表

記錄《劍指offer》中所有關(guān)于鏈表的題目，以及LeetCode中的相似題目

相關(guān)題目列表

題目

鏈表是面試中最常出現(xiàn)的題目之一，其特點是包含大量的指針操作，因此這對被面試者對指針的理解是否深入要求很高猪落。

面試題5： 從尾到頭打印鏈表

題目：輸入一個鏈表的頭結(jié)點，從尾到頭反過來打印出每個節(jié)點的值畴博。

題目分析

本題最暴力的方式是逐次遍歷鏈表輸出對應節(jié)點的值笨忌。但明顯這種方式的時間復雜度是我們無法接受的。有沒有高效的方法呢俱病。
其實很容易想到可以利用棧的先入后出的特性蜜唾。遍歷鏈表，并將遍歷到的元素依次push進棧庶艾，然后袁余，只需直接這個pop即為題目要求的從尾到頭打印鏈表。

參考代碼

#include<iostream>
#include<stack>
#include<vector>


using namespace std;

//創(chuàng)建單鏈表節(jié)點
struct ListNode
{
    int m_nValue;
    ListNode* m_pNext;
};

/*=======================在單向鏈表尾增添元素==========================*/

//考慮如果鏈表本身為空的時候咱揍，添加元素則新添加元素賦給pHead颖榜，
//如果不用二重指針，則在函數(shù)外不能改變*pHead的指向
void AddToTail(ListNode** pHead, int value)
{
    ListNode* pNew = new ListNode();    //使用new創(chuàng)建對象
    pNew->m_nValue = value;
    pNew->m_pNext = NULL;

    if (*pHead == NULL)     //如果鏈表為空，則直接賦值
        *pHead = pNew;
    else
    {
        ListNode* pNode = *pHead;   //鏈表不為空掩完，則通過移動指針pNode至最后
        while (pNode->m_pNext != NULL)
        {
            pNode = pNode->m_pNext;
        }

        pNode->m_pNext = pNew;  //添加元素
    }
}

/*=====================刪除給定值節(jié)點=================================*/
void RemoveNode(ListNode** pHead, int value)
{
    if (*pHead == NULL || pHead == NULL)      //
        return;

    ListNode* pToBeDeleted = NULL;  //臨時節(jié)點

    if ((*pHead)->m_nValue == value)
    {
        pToBeDeleted = *pHead;
        *pHead = (*pHead)->m_pNext;
    }
    else
    {
        ListNode* pNode = *pHead;
        while (pNode->m_pNext != NULL && pNode->m_pNext->m_nValue != value)
            pNode = pNode->m_pNext;

        if (pNode->m_pNext != NULL && pNode->m_pNext->m_nValue == value)
        {
            pToBeDeleted = pNode->m_pNext;
            pNode->m_pNext = pNode->m_pNext->m_pNext;
        }
    }

    if (pToBeDeleted != NULL)
    {
        delete pToBeDeleted;     //釋放內(nèi)存
        pToBeDeleted = NULL;     //釋放指針
    }
}

/*=========================測試類與main函數(shù)======================*/

/*
class Solution
{
public:
    vector<int> res;
    vector<int> PrintListFromTailToHead(ListNode *pHead)
    {
        if (pHead != NULL)
        {
            if (pHead->m_pNext != NULL)
            {
                PrintListFromTailToHead(pHead->m_pNext);
            }
            res.push_back(pHead->m_nValue);
        }
        return res;
    }
};
int main()
{
    ListNode list[4];
    list[0].m_nValue = 1;
    list[0].m_pNext = &list[1];
    list[1].m_nValue = 2;
    list[1].m_pNext = &list[2];
    list[2].m_nValue = 3;
    list[2].m_pNext = &list[3];
    list[3].m_nValue = 4;
    list[3].m_pNext = NULL;
    ListNode *node = *head;
    Solution result;
    vector<int> res = result.PrintListFromTailToHead(node);
    for (int i = 0; i < res.size(); ++i)
    {
        cout << res[i] << endl;
    }
    return 0;
}
*/


/*===========================從尾到頭打印鏈表========================*/
void PrintListfromTailtoHead(ListNode* pHead)
{
    std::stack<ListNode*> nodes;

    ListNode* pNode = pHead;
    while (pNode != NULL)
    {
        nodes.push(pNode);
        pNode = pNode->m_pNext;
    }

    while (!nodes.empty())
    {
        pNode = nodes.top();
        cout << pNode->m_nValue << " ";
        nodes.pop();
    }
}

/*======================遞歸方式=====================*/
void PrintListfromTailtoHead_Recursively(ListNode* pHead)
{
    if (pHead != NULL)
    {
        if (pHead->m_pNext != NULL)
        {
            PrintListfromTailtoHead_Recursively(pHead->m_pNext);
        }
        cout << pHead->m_nValue << " ";
    }
}

相似題目

可以在旁胙客網(wǎng) 劍指offer上完成對本題的測試。

面試題13： 在O(1)時間刪除鏈表節(jié)點

題目： 給定單向鏈表的頭指針和一個結(jié)點指針且蓬，定義一個函數(shù)在O(1)時間刪除該節(jié)點欣硼。

題目分析

上題中的參考代碼中給出了一般情況下刪除鏈表節(jié)點的代碼。但是由于鏈表的特殊性恶阴，我們首先需要遍歷鏈表找到該節(jié)點的上一個節(jié)點才能實施刪除操作诈胜。
這是由于我們要得到刪除節(jié)點的前一個節(jié)點才能對鏈表進行有效的刪除操作。那么本題的關(guān)鍵就在于是否存在一種方式可以不需要得到前一個節(jié)點而完成刪除操作呢冯事？
如果我們把下一個節(jié)點的內(nèi)容復制到需要刪除節(jié)點上覆蓋原來的內(nèi)容焦匈，再把下一個節(jié)點刪除，那就相當于完成了對節(jié)點的刪除操作昵仅。也就是說實際上我們是通過將該節(jié)點的下一節(jié)點刪除而替代了本節(jié)點的刪除缓熟。
但是，這樣做也存在一個問題摔笤，如果要刪除節(jié)點的下一個節(jié)點不存在怎么辦够滑，也就是要刪除節(jié)點本身是尾結(jié)點，這樣我們只能通過一般的刪除操作完成吕世。就是參考代碼如下：

參考代碼

#include<iostream>

using namespace std;

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

void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{
    if (!pListHead || !pToBeDeleted)
        return;

    //要刪除的結(jié)點不是尾結(jié)點
    if (pToBeDeleted->m_pNext != NULL)
    {
        ListNode* pNext = pToBeDeleted->m_pNext;
        pToBeDeleted->m_nValue = pNext->m_nValue;
        pToBeDeleted->m_pNext = pNext->m_pNext;

        delete pNext;
        pNext = NULL;
    }

    //只有一個結(jié)點彰触，刪除頭結(jié)點（也是尾結(jié)點）
    else if (*pListHead == pToBeDeleted)
    {
        delete pToBeDeleted;
        pToBeDeleted = NULL;
        *pListHead = NULL;
    }

    //鏈表有多個結(jié)點，刪除尾結(jié)點
    else
    {
        ListNode* pNode = *pListHead;
        while (pNode->m_pNext != pToBeDeleted)
        {
            pNode = pNode->m_pNext;
        }
        pNode->m_pNext = NULL;
        delete pToBeDeleted;
        pToBeDeleted = NULL;
    }
}

相似題目

本題與LeetCode中的237. Delete Node in a Linked List類似寞冯，另外LeetCode中還有一道刪除所有節(jié)點元素值為某一指定值的所有節(jié)點的題目203. Remove Linked List Elements。
這兩道題的參考代碼見：
LeetCode 237 code
LeetCode 203 code

面試題15： 鏈表中倒數(shù)第k個節(jié)點

題目： 輸入一個鏈表晚伙，輸出該鏈表中倒數(shù)第k個節(jié)點吮龄。為了符合大多數(shù)人的習慣，本題從1開始計數(shù)咆疗，即鏈表的尾結(jié)點是倒數(shù)第1個節(jié)點漓帚。

題目分析

本題可以先遍歷鏈表的到鏈表長度，從而可以確定倒數(shù)第k個節(jié)點的正向位置午磁，從而再通過一次遍歷得出題解尝抖，下面的代碼中采用的雙指針滑動其實也與這種方法本質(zhì)一樣,但需要注意算法的判定條件以保證其魯棒性。

參考代碼

#include<iostream>

using namespace std;

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

ListNode* FindKthToTail(ListNode* pListHead, int k)
{
    if (pListHead == NULL)  //如果輸入鏈表
        return NULL;
    if (k == 0)     //如果k==0
        return NULL;

    ListNode* pAhead = pListHead;
    ListNode* pBehind = pListHead;

    for (int i = 0; i < k - 1; ++i)
    {
        if (pAhead->m_pNext != NULL)      //判斷不能讓輸入的k值小于鏈表長度
        {
            pAhead = pAhead->m_pNext;
        }
        else       //證明k超出了鏈表長度
        {
            return NULL;
        }
    }

    while (pAhead->m_pNext != NULL)
    {
        pAhead = pAhead->m_pNext;
        pBehind = pBehind->m_pNext;
    }
    return pBehind;
}

int main()
{
    //->運算符需要前面是指針（指向類對象的指針）迅皇，.運算符需要前面是類的對象昧辽。
    ListNode List[5];
    List[0].m_nValue = 1;
    List[0].m_pNext = &List[1];
    List[1].m_nValue = 2;
    List[1].m_pNext = &List[2];
    List[2].m_nValue = 3;
    List[2].m_pNext = &List[3];
    List[3].m_nValue = 4;
    List[3].m_pNext = &List[4];
    List[4].m_nValue = 5;
    List[4].m_pNext = NULL;

    cout << FindKthToTail(List, 2)->m_nValue << endl;

    return 0;
}

相似題目

本題包含于LeetCode中的19. Remove Nth Node From End of List，LeetCode中的題目增加了對刪除該節(jié)點的要求登颓，參考代碼見：
LeetCode 19 code
還可以在沤淋瘢客網(wǎng) 劍指offer上完成對本題的練習。

面試題16： 反轉(zhuǎn)鏈表

題目： 定義一個函數(shù)，輸入一個鏈表的頭結(jié)點咕痛，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭結(jié)點痢甘。

題目分析

要實現(xiàn)一個鏈表的翻轉(zhuǎn)首先需要得到一個節(jié)點的前后節(jié)點，所以本題采用三指針滑動方法茉贡。這就涉及了大量的指針操作塞栅。

參考代碼

//三指針滑動法
#include<iostream>

using namespace std;

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

ListNode* ReversetList(ListNode* pHead)
{
    ListNode* pPrev = NULL;
    ListNode* pNode = pHead;
    ListNode* pNewHead = NULL;

    while (pNode != NULL)
    {
        ListNode *pNext = pNode->m_pNext;

        if (pNext == NULL)  //到達最后一個賦給新鏈表頭部
            pNewHead = pNode;

        pNode->m_pNext = pPrev;
        pPrev = pNode;
        pNode = pNext;
    }
    return pNewHead;
}

int main()
{
    ListNode List[5];

    List[0].m_nValue = 1;
    List[0].m_pNext = &List[1];
    List[1].m_nValue = 2;
    List[1].m_pNext = &List[2];
    List[2].m_nValue = 3;
    List[2].m_pNext = &List[3];
    List[3].m_nValue = 4;
    List[3].m_pNext = &List[4];
    List[4].m_nValue = 5;
    List[4].m_pNext = NULL;

    ListNode* node = List;

    while (node != NULL)
    {
        cout << node->m_nValue << " ";
        node = node->m_pNext;
    }

    cout << endl;

    node = ReversetList(List);  //鏈表必須以頭結(jié)點開始才能遍歷，所以要返回一個node

    while (node != NULL)
    {
        cout << node->m_nValue << " ";
        node = node->m_pNext;
    }

}

相似題目

本題與LeetCode中的206. Reverse Linked List完全一致腔丧；另外LeetCode中還有一道本題的引申92. Reverse Linked List II為翻轉(zhuǎn)鏈表的局部放椰。
這兩題的參考代碼見：
LeetCode 206 code
LeetCode 92 code
還可以在牛客網(wǎng) 劍指offer上完成對本題的練習悔据。

面試題17： 合并兩個排序的鏈表

題目： 輸入兩個遞增排序的鏈表庄敛，合并這兩個鏈表并使新鏈表中的節(jié)點仍然按照遞增排序。

題目分析

合并兩個鏈表的過程可以看成是一個不斷按照順序添加元素形成一個鏈表的過程科汗≡蹇荆可以以遞歸的方式解決。

參考代碼

#include<iostream>

using namespace std;

struct ListNode
{
    int val;
    ListNode* next;
};

class Solution
{
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if (pHead1 == NULL)
            return pHead2;
        if (pHead2 == NULL)
            return pHead1;

        ListNode* pNewHead = NULL;

        if (pHead1->val <= pHead2->val)
        {
            pNewHead = pHead1;
            pNewHead->next = Merge(pHead1->next, pHead2);
        }
        if (pHead1->val > pHead2->val)
        {
            pNewHead = pHead2;
            pNewHead->next = Merge(pHead1, pHead2->next);
        }
        return pNewHead;
    }
};

int main()
{
    ListNode List1[3];
    ListNode List2[3];

    List1[0].val = 1;
    List1[0].next = &List1[1];
    List1[1].val = 3;
    List1[1].next = &List1[2];
    List1[2].val = 5;
    List1[2].next = NULL;

    List2[0].val = 2;
    List2[0].next = &List2[1];
    List2[1].val = 4;
    List2[1].next = &List2[2];
    List2[2].val = 6;
    List2[2].next = NULL;

    Solution solu;

    ListNode* node = solu.Merge(List1, List2);

    while (node != NULL)
    {
        cout << node->val << " ";
        node = node->next;
    }
    return 0;
}

相似題目

本題與LeetCode中的21. Merge Two Sorted Lists完全一致头滔；另外LeetCode中還有一道本題的引申怖亭，即為合并k個排序鏈表23. Merge k Sorted Lists。這兩題的參考代碼見：
LeetCode 21 code
LeetCode 23 code
還可以在爬ぜ欤客網(wǎng) 劍指offer上完成對本題的練習兴猩。

面試題26： 復雜鏈表的復制

題目： 請實現(xiàn)函數(shù)，復制一個復雜鏈表早歇。在復雜鏈表中倾芝，每個節(jié)點除了有一個next指針指向下一個節(jié)點外，還有一個指針指向鏈表中的任意節(jié)點或者nullptr箭跳。

題目分析

本題可以采用三個步驟完成：
不妨設原始鏈表為N晨另，新鏈表為N'。
第一步谱姓，這個節(jié)點復制N借尿，并將N'放在每個復制節(jié)點后面。

第一步

第二步屉来，復制復雜指針路翻。N'對應節(jié)點的復雜指針應該在第一步得到鏈表上N的next。

第二步

第三步茄靠，拆分鏈表茂契。

第三步

參考代碼

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        CloneNodes(pHead);
        ConnectRandomNodes(pHead);
        return ReconnectNodes(pHead);
    }
private:
    //復制節(jié)點
    void CloneNodes(RandomListNode* pHead){
        RandomListNode* pNode = pHead;
        while (pNode != NULL){
            RandomListNode* pCloned = new RandomListNode(pNode->label);     //每次必須新建節(jié)點
            pCloned->label = pNode->label;
            pCloned->next = pNode->next;
            pCloned->random = NULL;

            pNode->next = pCloned;
            pNode = pCloned->next;
        }
    }

    //設置random指針
    void ConnectRandomNodes(RandomListNode* pHead){
        RandomListNode* pNode = pHead;
        while (pNode != NULL){
            RandomListNode* pCloned = pNode->next;
            if (pNode->random != NULL)
                pCloned->random = pNode->random->next;
            pNode = pCloned->next;
        }
    }

    //拆分鏈表
    RandomListNode* ReconnectNodes(RandomListNode* pHead){
        RandomListNode* pNode = pHead;
        RandomListNode* pClonedHead = NULL;
        RandomListNode* pClonedNode = NULL;

        if (pNode != NULL){     //處理頭結(jié)點
            pClonedHead = pClonedNode = pNode->next;
            pNode->next = pClonedNode->next;
            pNode = pNode->next;
        }
        while (pNode != NULL){
            pClonedNode->next = pNode->next;
            pClonedNode = pClonedNode->next;
            pNode->next = pClonedNode->next;
            pNode = pNode->next;
        }
        return pClonedHead;
    }
};

相似題目

本題與LeetCode中的138. Copy List with Random Pointer相似。參考代碼見：
LeetCode 138 code
還可以在趴客網(wǎng) 劍指offer上完成對本題的練習账嚎。

面試題27： 二叉樹與雙向鏈表

題目： 輸入一棵二叉搜索樹莫瞬，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點郭蕉，只能調(diào)整樹中結(jié)點指針的指向疼邀。

題目分析

根據(jù)BST與排序雙向鏈表的關(guān)系，原先指向左子結(jié)點的指針調(diào)整為鏈表中指向前一個結(jié)點的指針召锈，原先指向右子結(jié)點的指針調(diào)整為鏈表中指向后一個結(jié)點的指針旁振。

接下來我們考慮如何進行轉(zhuǎn)換。

根據(jù)BST中序遍歷有序的特點涨岁，我們采用中序遍歷算法從小到大遍歷二叉樹的每一個結(jié)點拐袜。當遍歷到根結(jié)點時，我們把樹看成3部分（如下圖所示）梢薪，值為10的結(jié)點蹬铺、根結(jié)點值為6的左子樹，根結(jié)點值為14的右子樹秉撇。根據(jù)排序鏈表的定義甜攀，值為10的節(jié)點將和它的左子樹的最大一個節(jié)點相連，同時與右子樹中最小節(jié)點相連琐馆。

根據(jù)中序遍歷的順序规阀，當我們遍歷轉(zhuǎn)換到根結(jié)點時，它的左子樹已經(jīng)轉(zhuǎn)換成一個排序鏈表了瘦麸，并且最后一個節(jié)點即為其中最大的結(jié)點谁撼。我們把8與10相連即可。接著遍歷轉(zhuǎn)換右子樹滋饲，并把根結(jié)點和右子樹中最小的結(jié)點相連厉碟。

參考代碼

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode* pLastNodeInList = NULL;
        ConverNode(pRootOfTree, &pLastNodeInList);  //因為函數(shù)形參是二重指針，所以需要用取地址符

        TreeNode* pHeadOfList = pLastNodeInList;
        while (pHeadOfList != NULL && pHeadOfList->left != NULL)
            pHeadOfList = pHeadOfList->left;
        return pHeadOfList;
    }
private:
    //類似于中序遍歷
    void ConverNode(TreeNode* pNode, TreeNode** pLastNodeInList){   //因為需要對pLastNodeInList進行動態(tài)改變屠缭，所以需要用二重指針
        if (pNode == NULL)
            return;

        TreeNode* pCurrent = pNode;
        if (pCurrent->left != NULL)
            ConverNode(pCurrent->left, pLastNodeInList);

        pCurrent->left = *pLastNodeInList;

        if (*pLastNodeInList != NULL)
            (*pLastNodeInList)->right = pCurrent;

        *pLastNodeInList = pCurrent;

        if (pCurrent->right != NULL)
            ConverNode(pCurrent->right, pLastNodeInList);
    }
};

相似題目

本題與LeetCode中的109. Convert Sorted List to Binary Search Tree類似箍鼓，其是將單鏈表轉(zhuǎn)化為BST。
還可以在盼鹚客網(wǎng) 劍指offer上完成對本題的練習袄秩。

面試題37： 兩個鏈表的第一個公共結(jié)點

題目： 輸入兩個鏈表阵翎，找出它們的第一個公共結(jié)點。

題目分析

本題是典型的快慢指針應用問題，要求得兩個鏈表的公共節(jié)點可以先得到兩個鏈表的長度得问，則通過長度可以進行快慢指針的設置页藻，例如假如l1的長度為m，l2的長度為n贰军，且不妨設m>n玻蝌，于是可以設置在較長的鏈表l1上先走m-n步蟹肘；在同時便利，則到達第一個相同的節(jié)點即為第一個公共節(jié)點俯树。

參考代碼

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == NULL || pHead2 == NULL)
            return NULL;
        int pHead1_size = 0;
        int pHead2_size = 0;

        ListNode* pNode1 = pHead1;
        ListNode* pNode2 = pHead2;
        while (pNode1 != NULL){     //得到pHead1的size
            pHead1_size++;
            pNode1 = pNode1->next;
        }
        while (pNode2 != NULL){     //得到pHead2的size
            pHead2_size++;
            pNode2 = pNode2->next;
        }

        int length = pHead1_size - pHead2_size;
        //cout << length << endl;
        if (length > 0){
            pNode2 = pHead2;
            pNode1 = pHead1;
            while (length != 0){
                pNode1 = pNode1->next;
                length--;
            }
        }
        else if (length < 0){
            pNode1 = pHead1;
            pNode2 = pHead2;
            while (length != 0){
                pNode2 = pNode2->next;
                length++;
            }
        }
        else if (length == 0){
            pNode1 = pHead1;
            pNode2 = pHead2;
        }

        while (pNode1 != pNode2){
            pNode1 = pNode1->next;
            pNode2 = pNode2->next;
        }
        return pNode1;

    }
};

相似題目

本題與LeetCode中的160. Intersection of Two Linked Lists
一致帘腹。參考代碼見：
LeetCode 160 code
還可以在牛客網(wǎng) 劍指offer上完成對本題的練習许饿。

面試題45： 圓圈中最后剩下的數(shù)字

題目： 0,1,...,n-1這n個數(shù)字排成一個圓圈阳欲，從數(shù)字0開始每次從這個圓圈里刪除第m個數(shù)字。求出這個圓圈里剩下的最后一個數(shù)字陋率。

題目分析

本題是有名的約瑟夫環(huán)問題球化，有兩種常見的解法。
第一種是以環(huán)形鏈表模擬圓圈的經(jīng)典解法瓦糟，第二種是分析環(huán)的規(guī)律求解筒愚。下面介紹經(jīng)典的解法。
如下圖所示為環(huán)形鏈表模擬圓圈示意圖：

環(huán)形鏈表模擬圓圈示意圖

參考代碼中以std::list來實現(xiàn)環(huán)形鏈表菩浙。由于list本身不是一個環(huán)形結(jié)構(gòu)巢掺，因此每次迭代器掃描到鏈表末尾的時候，都要將迭代器移到鏈表的頭部來模擬環(huán)形鏈表的遍歷芍耘。

參考代碼

#include<iostream>
#include<list>

using namespace std;

/*===========常規(guī)做法:循環(huán)鏈表==============*/
class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if (n < 1 || m < 1)
            return -1;
        list<int> numbers;
        for (int i = 0; i < n; ++i){
            numbers.push_back(i);
        }

        list<int>::iterator current = numbers.begin();
        while (numbers.size() > 1){
            for (int i = 1; i < m; ++i){    //找到要刪除的元素
                current++;
                if (current == numbers.end())   //尾后迭代器不是數(shù)組中最后一個元素址遇，而是最后一個元素后面的一個地址
                    current = numbers.begin();
            }

            list<int>::iterator next = ++current;   //list的vector不支持+
            if (next == numbers.end())
                next = numbers.begin();
            --current;
            numbers.erase(current);
            current = next;
        }
        return *current;
    }
};

int main()
{
    Solution solu;
    cout << solu.LastRemaining_Solution(5,3) << endl;

    return 0;
}

相似題目

可以在牛客網(wǎng) 劍指offer上完成對本題的練習斋竞。

面試題56： 鏈表中環(huán)的入口結(jié)點

題目： 一個鏈表中包含環(huán)倔约，如何找出環(huán)的入口結(jié)點？

題目分析

本題可以分解為幾個子題目解決：
首先坝初，通過快慢指針找到處于鏈表環(huán)中的某個節(jié)點浸剩。
然后，通過這個節(jié)點可以確定鏈表環(huán)的長度鳄袍。
最后绢要，根據(jù)得到環(huán)的長度，可以設置快慢指針拗小，找到兩個指針第一次相遇的節(jié)點即為環(huán)的入口節(jié)點重罪。

參考代碼

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if (pHead == NULL)
            return NULL;
        ListNode* meetingNode = MeetingNode(pHead);
        if (meetingNode == NULL)
            return NULL;

        int length = 1;
        ListNode* pNode = meetingNode->next;
        while (pNode != meetingNode){
            pNode = pNode->next;
            length++;
        }
        //此時length為環(huán)的長度

        ListNode* pNode1 = pHead;
        ListNode* pNode2 = pHead;
        for (int i = 0; i < length; ++i){
            pNode2 = pNode2->next;
        }

        while (pNode1 != pNode2){
            pNode1 = pNode1->next;
            pNode2 = pNode2->next;
        }
        return pNode1;
    }
private:
    //通過快慢指針判斷是否有環(huán)，并且返回環(huán)中的一個節(jié)點為求環(huán)的長度做準備
    ListNode* MeetingNode(ListNode* pHead){
        if (pHead == NULL)
            return NULL;
        ListNode* pSlow = pHead->next;
        if (pSlow == NULL)
            return NULL;
        ListNode* pFirst = pSlow->next;

        while (pSlow != NULL && pFirst != NULL){
            if (pSlow == pFirst)
                return pSlow;
            pSlow = pSlow->next;
            pFirst = pFirst->next;

            if (pFirst != NULL)
                pFirst = pFirst->next;      //快指針每次走兩步
        }
        return NULL;    //如果不滿足while條件哀九，則證明沒有環(huán)剿配，返回NULL
    }
};

相似題目

LeetCode中有141. Linked List Cycle為判斷鏈表中是否有環(huán)；142. Linked List Cycle II與本題完全一致阅束。這兩題的參考代碼見：
LeetCode 141 code
LeetCode 142 code

可以在藕襞撸客網(wǎng) 劍指offer上完成對本題的練習。

面試題57： 刪除鏈表中重復的結(jié)點

題目： 在一個排序的鏈表中息裸，如何刪除重復的結(jié)點蝇更？

題目分析

本題需要考慮頭結(jié)點的可刪除性沪编。從而需要在頭結(jié)點前設置哨兵節(jié)點，從而遍歷鏈表完成刪除操作年扩。

參考代碼

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if (pHead == NULL)
            return NULL;
        ListNode* pPre = NULL;
        ListNode* pNode = pHead;

        while (pNode != NULL){
            ListNode* pNext = pNode->next;
            bool del = false;
            if (pNext != NULL && pNext->val == pNode->val)
                del = true;

            if (!del){  //不需要刪除
                pPre = pNode;
                pNode = pNode->next;
            }
            else{   //需要刪除
                int value = pNode->val;
                ListNode* pToBeDel = pNode;
                while (pToBeDel != NULL && pToBeDel->val == value){
                    pNext = pToBeDel->next;
                    delete pToBeDel;
                    pToBeDel = NULL;

                    pToBeDel = pNext;
                }

                if(pPre == NULL)
                    pHead = pNext;
                else
                    pPre->next = pNext;

                pNode = pNext;
            }
        }
        return pHead;
    }
};

class Solution2 {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        ListNode* first = new ListNode(-1); //設置一個起始位置蚁廓，并初始化為負數(shù)
        first->next = pHead;
        ListNode* pNode = pHead;
        ListNode* pre = first;

        while (pNode != NULL && pNode->next != NULL){
            if (pNode->val == pNode->next->val){
                //跳過重復元素
                int val = pNode->val;
                while (pNode != NULL && val == pNode->val){
                    pNode = pNode->next;
                }
                pre->next = pNode;
            }
            else{
                pre = pNode;
                pNode = pNode->next;
            }
        }
        return first->next;
    }
};

相似題目

本題與LeetCode中的82. Remove Duplicates from Sorted List II完全一致，另外LeetCode中還有一道本題的變型厨幻，每個重復元素留下一個纳令，即一道鏈表去重題83. Remove Duplicates from Sorted List
，這兩題的參考代碼見：
LeetCode 82 code
LeetCode 83 code
還可以在趴烁欤客網(wǎng) 劍指offer上完成對本題的練習平绩。

【參考】
[1]《劍指offer》

歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明出處：wenmingxing 《劍指offer》鏈表專題