走的那么干脆 2019-04-07 15:28 采纳率: 100%
浏览 570
已采纳

链表操作中即使函数传入的是链表指针，若根节点没有改变，链表也会改变？

事情是这样的，今天刷剑指offer时，对书中的内容产生了一点点小质疑，所以就拿VS2013和Code::Blocks都跑了一遍，两者结果是一致的，但程序执行的结果让我有点疑惑。

题目如下：

在一个排序的链表中，删除链表中重复的节点。

例如: 1->2->3->3->4->4->5，删除后的结果为1->2->5。

书中说由于头节点也可能被删除，所以函数应申明为

void deleteDuplication(ListNode** pHead)

而不是

void deleteDuplication(ListNode* pHead)

然后我就试了一下第二者，发现如果函数deleteDuplication处理完毕后，如果以形参形式传入的根节点pHead没有发生改变，则在main()函数里打印出链表的时候，链表和处理前的不一样了（即发生了改变）；但如果根节点发生了改变，在mian()函数里打印结果却发现链表和处理前一样（即没有发生改变）。

所以我就懵了，按书上这句话的意思，应该就是如果传入的根节点为链表指针（即ListNode* pHead），则链表应该出了函数也不会发生任何变化。

但实际的结果却是由根节点是否发生了变化而决定，求大家赐教哈。

（注：ListNode** pHead是正常的，却是是出了函数也会改变链表实参本身）。

还有一个问题就是如果在函数里delete掉形参链表一个节点，也会影响链表实参本身，这又是什么原理。

完整代码如下：

1）当形参根节点未发生变化时：

#include <stdio.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    void deleteDuplication(ListNode* pHead)
    {
        if (pHead == NULL || pHead->next == NULL)
            return;
        ListNode* pNode = pHead;
        ListNode* preNode = NULL;
        while (pNode)
        {
            bool deleteflag = false;
            if (pNode->next && pNode->val == pNode->next->val)
                deleteflag = true;

            if (!deleteflag)
            {
                preNode = pNode;
                pNode = pNode->next;
            }
            else
            {
                int value = pNode->val;
                ListNode* next = pNode;
                while (pNode && pNode->val == value)
                {
                    next = pNode->next;
                    //delete pNode;
                    pNode = next;
                }
                if (preNode == NULL)
                    pHead = pNode;
                else
                    preNode->next = pNode;
            }
        }
    }
};
int main()
{
    //生成链表1->2->3->3->4->4->5
    ListNode* pHead = new ListNode(1);
    pHead->next = new ListNode(2);
    ListNode* pNode = pHead;
    pNode = pNode->next;
    pNode->next = new ListNode(3);
    pNode = pNode->next;
    pNode->next = new ListNode(3);
    pNode = pNode->next;
    pNode->next = new ListNode(4);
    pNode = pNode->next;
    pNode->next = new ListNode(4);
    pNode = pNode->next;
    pNode->next = new ListNode(5);


    Solution so;

    so.deleteDuplication(pHead);
    pNode = pHead;
    while (pNode)
    {
        printf("%d ", pNode->val);
        pNode = pNode->next;
    }
    printf("\n");

    return 0;
}

输出结果如下图：

图片说明

2）当形参根节点发生变化时：

#include <stdio.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    void deleteDuplication(ListNode* pHead)
    {
        if (pHead == NULL || pHead->next == NULL)
            return;
        ListNode* pNode = pHead;
        ListNode* preNode = NULL;
        while (pNode)
        {
            bool deleteflag = false;
            if (pNode->next && pNode->val == pNode->next->val)
                deleteflag = true;

            if (!deleteflag)
            {
                preNode = pNode;
                pNode = pNode->next;
            }
            else
            {
                int value = pNode->val;
                ListNode* next = pNode;
                while (pNode && pNode->val == value)
                {
                    next = pNode->next;
                    //delete pNode;
                    pNode = next;
                }
                if (preNode == NULL)
                    pHead = pNode;
                else
                    preNode->next = pNode;
            }
        }
    }
};
int main()
{
    //生成链表1->1->3->3->4->4->5
    ListNode* pHead = new ListNode(1);
    pHead->next = new ListNode(1);
    ListNode* pNode = pHead;
    pNode = pNode->next;
    pNode->next = new ListNode(3);
    pNode = pNode->next;
    pNode->next = new ListNode(3);
    pNode = pNode->next;
    pNode->next = new ListNode(4);
    pNode = pNode->next;
    pNode->next = new ListNode(4);
    pNode = pNode->next;
    pNode->next = new ListNode(5);


    Solution so;

    so.deleteDuplication(pHead);
    pNode = pHead;
    while (pNode)
    {
        printf("%d ", pNode->val);
        pNode = pNode->next;
    }
    printf("\n");

    return 0;
}

输出结果如下图：

图片说明

3）当函数中delete掉形参链表的一个节点时

无论形参根节点是否改变，实现链表都会发生变化。且在VS2013下，形参根节点发生改变时，程序会报内存访问出错。

#include <stdio.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:


    void deleteDuplication(ListNode* pHead)
    {
        if (pHead == NULL || pHead->next == NULL)
            return;
        ListNode* pNode = pHead;
        ListNode* preNode = NULL;
        while (pNode)
        {
            bool deleteflag = false;
            if (pNode->next && pNode->val == pNode->next->val)
                deleteflag = true;

            if (!deleteflag)
            {
                preNode = pNode;
                pNode = pNode->next;
            }
            else
            {
                int value = pNode->val;
                ListNode* next = pNode;
                while (pNode && pNode->val == value)
                {
                    next = pNode->next;
                    delete pNode; //删除当前节点
                    pNode = next; 
                }
                if (preNode == NULL)
                    pHead = pNode;
                else
                    preNode->next = pNode;
            }
        }
    }
};
int main()
{

    ListNode* pHead = new ListNode(1);
    pHead->next = new ListNode(1);
    ListNode* pNode = pHead;
    pNode = pNode->next;
    pNode->next = new ListNode(3);
    pNode = pNode->next;
    pNode->next = new ListNode(3);
    pNode = pNode->next;
    pNode->next = new ListNode(4);
    pNode = pNode->next;
    pNode->next = new ListNode(4);
    pNode = pNode->next;
    pNode->next = new ListNode(5);


    Solution so;
    so.deleteDuplication(pHead);
    pNode = pHead;
    while (pNode)
    {
        printf("%d ", pNode->val);
        pNode = pNode->next;
    }
    printf("\n");

    return 0;
}

图片说明

  • 写回答

1条回答 默认 最新

  • threenewbee 2019-04-07 16:03
    关注

    如果问题解决，请点采纳，谢谢

    #include <stdio.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    void deleteDuplication(ListNode** pHead)
    {
        if ((*pHead) == NULL || (*pHead)->next == NULL)
            return;
        ListNode* pNode = *pHead;
        ListNode* preNode = NULL;
        while (true)
        {           
            if (preNode == NULL || preNode->val != pNode->val)
            {
                preNode = pNode;
                pNode = pNode->next;
            }
            else
            {
                if (preNode == NULL)
                {
                    *pHead = pNode->next;
                }
                ListNode* del = pNode;
                preNode->next = pNode->next;
                pNode = preNode->next;
                delete(del);
            }
            if (!pNode) break;
        }
    }
};
int main()
{
    //生成链表1->1->3->3->4->4->5
    ListNode* pHead = new ListNode(1);
    pHead->next = new ListNode(1);
    ListNode* pNode = pHead;
    pNode = pNode->next;
    pNode->next = new ListNode(3);
    pNode = pNode->next;
    pNode->next = new ListNode(3);
    pNode = pNode->next;
    pNode->next = new ListNode(4);
    pNode = pNode->next;
    pNode->next = new ListNode(4);
    pNode = pNode->next;
    pNode->next = new ListNode(5);

    Solution so;

    so.deleteDuplication(&pHead);
    pNode = pHead;
    while (pNode)
    {
        printf("%d ", pNode->val);
        pNode = pNode->next;
    }
    printf("\n");

    return 0;
}
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题？

悬赏问题

  • ¥15 luckysheet
  • ¥15 ZABBIX6.0L连接数据库报错，如何解决？(操作系统-centos)
  • ¥15 找一位技术过硬的游戏pj程序员
  • ¥15 matlab生成电测深三层曲线模型代码
  • ¥50 随机森林与房贷信用风险模型
  • ¥50 buildozer打包kivy app失败
  • ¥30 在vs2022里运行python代码
  • ¥15 不同尺寸货物如何寻找合适的包装箱型谱
  • ¥15 求解 yolo算法问题
  • ¥15 虚拟机打包apk出现错误