当前位置 博文首页 > Scissors_初夏的博客:初夏小谈:删除单链表中重复的结点1.0(链
初次接触删除链表中的重复结点问题,那就从基础的操作做起。删除连续相同的数据的结点问题,删除结点,那肯定要就删除的结点摘除,把后面链子接上就可以了。所以删除时就需要记录它的前一个结点一边可以连接后面的链表。
如果重复的结点可能有很多个,那么就要再标记重复后的下一个结点(与重复结点数据不同)
对此就可以使用三指针法进行相关操作。
在三指针法操作时,第一个指针是指向开始重复结点的上一个结点,如果开始就是重复结点那就让第一个指针指向NULL,第二个指针指向重复的第一个结点,第三个指向重复的第二个结点,如果后面还有重复的结点就继续让第三个指针往下一个结点移动,直到遇到不是重复结点或NULL停止。
代码如下:
void DelRepetitionLinkList(LinkList* first)
{
assert(first);
if (first->head == NULL)
{
return;
}
LinkListNode* ptr0 = NULL;//指向要重复结点的前一个
LinkListNode* ptr1 = first->head;//指向重复结点的第一个
LinkListNode* ptr2 = first->head->next;//指向重复结点的下一个不重复结点
while (ptr1->next != NULL)
{
//没有重复的结点时让三个指针依次往前走
if (ptr1->data != ptr2->data)
{
ptr0 = ptr1;
ptr1 = ptr2;
ptr2 = ptr2->next;
}
else
{
LinkListNode* ptr;
while (ptr1->data == ptr2->data)
{
//遇到重复的结点数据时,只让ptr2指针往后走,边走边释放
if (ptr1->next != NULL)
{
ptr = ptr2;
ptr2 = ptr2->next;
free(ptr);
ptr1->next = ptr2;
}
//处理重复结点的下一个刚好为空的情况
if(ptr2 == NULL)
{
//ptr2为空,指针ptr1走到链表尽头---处理重复链表已完成。(分为两种情况)
if (ptr0 != NULL)//一、当链表第一个节点不是重复结点时 例子:1 2 2 2 2 2 2
{
free(ptr0->next);
ptr1 = ptr2;
ptr0->next = ptr1;
return;
}
else //二、当链表第一个节点是重复结点时 例子:2 2 2 2 2 2 2
{
free(ptr1);
ptr1 = ptr2;
ptr0 = ptr1;
first->head = ptr0;
return;
}
}
}
//处理链表重复结点的下一个不是空(即有结点)时的情况(分为两种)
if (ptr0 != NULL)//一、ptr0不为空,即第一个节点不是重复结点时 例子:1 2 2 2 2 2 3 4
{
free(ptr0->next);
ptr1 = ptr2;
ptr0->next = ptr1;
if (ptr1 == NULL)
{
return;
}
if (ptr2 != NULL)
{
ptr2 = ptr2->next;
}
}
else //二、ptr0为空,即第一个节点是重复结点时 例子:2 2 2 2 2 2 3 4
{
free(ptr1);
ptr1 = ptr2;
ptr0 = ptr1;
first->head = ptr0;
if (ptr2 == NULL)
{
return;
}
}
}
}
}
cs初级删除重复结点时需要注意对边界问题的考虑。对各种边界问题应注意分类,这样不至于思路混乱。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?珍源码