《剑指offer》链表专题

链表

记录《剑指offer》中所有关于链表的题目，以及LeetCode中的相似题目

相关题目列表

index description key words done date
5 从尾到头打印链表 栈的应用 Y 18-2-1
13 在O(1)时间删除链表结点 删除结点 Y 18-2-1
15 链表中倒数第k个结点 双指针 Y 18-2-1
16 反转链表 反转 Y 18-2-2
17 合并两个排序的链表 递归合并 Y 18-2-2
26 复杂链表的复制 链表复制 Y 18-2-2
27 二叉搜索树与双向链表 与链表的关系 Y 18-4-2
37 两个链表的第一个公共结点 快慢指针 Y 18-2-3
45 圆圈中最后剩下的数字 约瑟夫环 Y 18-2-14
56 链表中环的入口结点 快慢指针 Y 18-2-3
57 删除链表中重复的结点 删除节点 Y 18-2-14

题目

链表是面试中最常出现的题目之一，其特点是包含大量的指针操作，因此这对被面试者对指针的理解是否深入要求很高。

面试题5： 从尾到头打印链表

题目：输入一个链表的头结点，从尾到头反过来打印出每个节点的值。

题目分析

本题最暴力的方式是逐次遍历链表输出对应节点的值。但明显这种方式的时间复杂度是我们无法接受的。有没有高效的方法呢。
其实很容易想到可以利用栈的先入后出的特性。遍历链表，并将遍历到的元素依次push进栈，然后，只需直接这个pop即为题目要求的从尾到头打印链表。

参考代码

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


using namespace std;

//创建单链表节点
struct ListNode
{
    int m_nValue;
    ListNode* m_pNext;
};

/*=======================在单向链表尾增添元素==========================*/

//考虑如果链表本身为空的时候，添加元素则新添加元素赋给pHead，
//如果不用二重指针，则在函数外不能改变*pHead的指向
void AddToTail(ListNode** pHead, int value)
{
    ListNode* pNew = new ListNode();    //使用new创建对象
    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;  //添加元素
    }
}

/*=====================删除给定值节点=================================*/
void RemoveNode(ListNode** pHead, int value)
{
    if (*pHead == NULL || pHead == NULL)      //
        return;

    ListNode* pToBeDeleted = NULL;  //临时节点

    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;     //释放内存
        pToBeDeleted = NULL;     //释放指针
    }
}

/*=========================测试类与main函数======================*/

/*
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 << " ";
    }
}

相似题目

可以在牛客网 剑指offer上完成对本题的测试。

面试题13： 在O(1)时间删除链表节点

题目： 给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该节点。

题目分析

上题中的参考代码中给出了一般情况下删除链表节点的代码。但是由于链表的特殊性，我们首先需要遍历链表找到该节点的上一个节点才能实施删除操作。
这是由于我们要得到删除节点的前一个节点才能对链表进行有效的删除操作。那么本题的关键就在于是否存在一种方式可以不需要得到前一个节点而完成删除操作呢？
如果我们把下一个节点的内容复制到需要删除节点上覆盖原来的内容，再把下一个节点删除，那就相当于完成了对节点的删除操作。也就是说实际上我们是通过将该节点的下一节点删除而替代了本节点的删除。
但是，这样做也存在一个问题，如果要删除节点的下一个节点不存在怎么办，也就是要删除节点本身是尾结点，这样我们只能通过一般的删除操作完成。就是参考代码如下：

参考代码

#include<iostream>

using namespace std;

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

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

    //要删除的结点不是尾结点
    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;
    }

    //只有一个结点，删除头结点（也是尾结点）
    else if (*pListHead == pToBeDeleted)
    {
        delete pToBeDeleted;
        pToBeDeleted = NULL;
        *pListHead = NULL;
    }

    //链表有多个结点，删除尾结点
    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中还有一道删除所有节点元素值为某一指定值的所有节点的题目203. Remove Linked List Elements。
这两道题的参考代码见：
LeetCode 237 code
LeetCode 203 code

面试题15： 链表中倒数第k个节点

题目： 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个节点。

题目分析

本题可以先遍历链表的到链表长度，从而可以确定倒数第k个节点的正向位置，从而再通过一次遍历得出题解，下面的代码中采用的双指针滑动其实也与这种方法本质一样,但需要注意算法的判定条件以保证其鲁棒性。

参考代码

#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中的题目增加了对删除该节点的要求，参考代码见：
LeetCode 19 code
还可以在牛客网 剑指offer上完成对本题的练习。

面试题16： 反转链表

题目： 定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

题目分析

要实现一个链表的翻转首先需要得到一个节点的前后节点，所以本题采用三指针滑动方法。这就涉及了大量的指针操作。

参考代码

//三指针滑动法
#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);  //链表必须以头结点开始才能遍历，所以要返回一个node

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

}

相似题目

本题与LeetCode中的206. Reverse Linked List完全一致；另外LeetCode中还有一道本题的引申92. Reverse Linked List II为翻转链表的局部。
这两题的参考代码见：
LeetCode 206 code
LeetCode 92 code
还可以在牛客网 剑指offer上完成对本题的练习。

面试题17： 合并两个排序的链表

题目： 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然按照递增排序。

题目分析

合并两个链表的过程可以看成是一个不断按照顺序添加元素形成一个链表的过程。可以以递归的方式解决。

参考代码

#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
还可以在牛客网 剑指offer上完成对本题的练习。

面试题26： 复杂链表的复制

题目： 请实现函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个next指针指向下一个节点外，还有一个指针指向链表中的任意节点或者nullptr。

题目分析

本题可以采用三个步骤完成：
不妨设原始链表为N，新链表为N'。
第一步，这个节点复制N，并将N'放在每个复制节点后面。

第一步

第二步，复制复杂指针。N'对应节点的复杂指针应该在第一步得到链表上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:
    //复制节点
    void CloneNodes(RandomListNode* pHead){
        RandomListNode* pNode = pHead;
        while (pNode != NULL){
            RandomListNode* pCloned = new RandomListNode(pNode->label);     //每次必须新建节点
            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){     //处理头结点
            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
还可以在牛客网 剑指offer上完成对本题的练习。

面试题27： 二叉树与双向链表

题目： 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

题目分析

根据BST与排序双向链表的关系，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子结点的指针调整为链表中指向后一个结点的指针。

接下来我们考虑如何进行转换。

根据BST中序遍历有序的特点，我们采用中序遍历算法从小到大遍历二叉树的每一个结点。当遍历到根结点时，我们把树看成3部分（如下图所示），值为10的结点、根结点值为6的左子树，根结点值为14的右子树。根据排序链表的定义，值为10的节点将和它的左子树的最大一个节点相连，同时与右子树中最小节点相连。

根据中序遍历的顺序，当我们遍历转换到根结点时，它的左子树已经转换成一个排序链表了，并且最后一个节点即为其中最大的结点。我们把8与10相连即可。接着遍历转换右子树，并把根结点和右子树中最小的结点相连。

参考代码

/*
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);  //因为函数形参是二重指针，所以需要用取地址符

        TreeNode* pHeadOfList = pLastNodeInList;
        while (pHeadOfList != NULL && pHeadOfList->left != NULL)
            pHeadOfList = pHeadOfList->left;
        return pHeadOfList;
    }
private:
    //类似于中序遍历
    void ConverNode(TreeNode* pNode, TreeNode** pLastNodeInList){   //因为需要对pLastNodeInList进行动态改变，所以需要用二重指针
        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类似，其是将单链表转化为BST。
还可以在牛客网 剑指offer上完成对本题的练习。

面试题37： 两个链表的第一个公共结点

题目： 输入两个链表，找出它们的第一个公共结点。

题目分析

本题是典型的快慢指针应用问题，要求得两个链表的公共节点可以先得到两个链表的长度，则通过长度可以进行快慢指针的设置，例如假如l1的长度为m，l2的长度为n，且不妨设m>n，于是可以设置在较长的链表l1上先走m-n步；在同时便利，则到达第一个相同的节点即为第一个公共节点。

参考代码

/*
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
还可以在牛客网 剑指offer上完成对本题的练习。

面试题45： 圆圈中最后剩下的数字

题目： 0,1,...,n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

题目分析

本题是有名的约瑟夫环问题，有两种常见的解法。
第一种是以环形链表模拟圆圈的经典解法，第二种是分析环的规律求解。下面介绍经典的解法。
如下图所示为环形链表模拟圆圈示意图：

环形链表模拟圆圈示意图

参考代码中以std::list来实现环形链表。由于list本身不是一个环形结构，因此每次迭代器扫描到链表末尾的时候，都要将迭代器移到链表的头部来模拟环形链表的遍历。

参考代码

#include<iostream>
#include<list>

using namespace std;

/*===========常规做法:循环链表==============*/
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())   //尾后迭代器不是数组中最后一个元素，而是最后一个元素后面的一个地址
                    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;
}

相似题目

可以在牛客网 剑指offer上完成对本题的练习。

面试题56： 链表中环的入口结点

题目： 一个链表中包含环，如何找出环的入口结点？

题目分析

本题可以分解为几个子题目解决：
首先，通过快慢指针找到处于链表环中的某个节点。
然后，通过这个节点可以确定链表环的长度。
最后，根据得到环的长度，可以设置快慢指针，找到两个指针第一次相遇的节点即为环的入口节点。

参考代码

/*
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为环的长度

        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:
    //通过快慢指针判断是否有环，并且返回环中的一个节点为求环的长度做准备
    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条件，则证明没有环，返回NULL
    }
};

相似题目

LeetCode中有141. Linked List Cycle为判断链表中是否有环；142. Linked List Cycle II与本题完全一致。这两题的参考代码见：
LeetCode 141 code
LeetCode 142 code

可以在牛客网 剑指offer上完成对本题的练习。

面试题57： 删除链表中重复的结点

题目： 在一个排序的链表中，如何删除重复的结点？

题目分析

本题需要考虑头结点的可删除性。从而需要在头结点前设置哨兵节点，从而遍历链表完成删除操作。

参考代码

/*
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); //设置一个起始位置，并初始化为负数
        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
还可以在牛客网 剑指offer上完成对本题的练习。

【参考】
[1]《剑指offer》

欢迎转载，转载请注明出处：wenmingxing 《剑指offer》链表专题

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,242评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,769评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,484评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,133评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,007评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,080评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,496评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,190评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,464评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,549评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,330评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,205评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,567评论 3赞 298
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,889评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,160评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,475评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,650评论 2赞 335