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

事情是这样的,今天刷剑指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;
}

图片说明

c++

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 (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;
}
caozhy
贵阳老马马善福专业维修游泳池堵漏防水工程 顺便说下,我的程序是删除重复节点的第一个,这种情况需要传出pHeader,但是我想了下,也可以删除后面一个,这样就无论头节点还是后面的重复,都不需要修改pHead了。
7 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!

相似问题

2
请问这个删除节点函数有什么问题,编译链接通过运行崩溃
3
线索二叉树,怎么可能把二叉树变为双向链表呢?
4
c语言程序设计-将文件内容赋到一个链表里 然后写一个增加节点的函数 将新增加的节点连到那个链表后面
1
关于链表函数中存在的bug
1
c语言链表问题,希望能在10号之前得到解答
1
链表插入数据:为什么在成员函数insert中还要判断指针head是否为空指针?
1
C++在链表递归的过程中使用临时节点并且置NULL,那么二叉树需要吗?
1
这个链表排序的函数哪里有问题,下面的注释是输入,从大到小排序后输出
1
红黑树最坏情况为何不是退变为链表的情况?
0
链表中,dummyhead是怎么做到自动更新到新的节点的呢?
2
为什么用while循环至链表某尾时程序不再运行?
4
问一个很愚蠢的基础问题,p=p->next链表循环里,为什么这样不会覆盖掉链表的值啊
1
从txt文件中读取数据存入到链表,即使文件没有内容也会存上数字和乱码
1
c语言,为什么用fread 读入文件 链表 每次都会多一个节点?
1
单链表的一些操作,没有输出。不知道哪里错了!!!求大哥帮忙!
1
C语言求助:输入一个字符串,将其中的字母字符输入一个链表,将其中的数字字符输入另一个链表。
1
java链表添加头节点方法没有用
2
关于C++链表指针问题,望解答
1
双向链表,尾插函数用了之后得到结果不正常?
0
链表排序出了问题,求大佬帮忙看看