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

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

图片说明

查看全部
qq_21368481
走的那么干脆
2019/04/07 15:28
  • c++
  • 点赞
  • 收藏
  • 回答
    私信
满意答案
查看全部

1个回复