链表操作中函数传入链表指针，若根节点没有改变，链表也会改变？
事情是这样的，今天刷剑指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;
}
查看15道真题和解析