C语⾔：删除链表中的重复节点（⼆）
假设要求删除有序链表中的重复节点，重复节点⼀个不留。
思路：
⼀. 需要3个节点来标记位置，分别是当前节点current，它的前向节点pre和它的后继节点next；
⼆. current节点从链表的头节点开始依次右移，pre初始化为空；
三. 若current节点不为空，判断next节点是否为空、next节点的val与current的val是否相同；
1. 若next节点不为空，且next节点的val与current的val相同
(1). 建⽴node节点，初始化为current，删除从node开始所有与current的val相同的节点
(2). 然后判断pre是否为空
a. pre为空
说明头节点是重复节点，已被删除，令head指向当前链表中的第⼀个未被删除的节点next；
b.pre不为空
令pre指向next，使链表保持连接
(3). 然后更新current,，使它指向next节点
2. 否则
pre指向当前节点current，current指向next节点；
与单链表操作有关的代码放在头⽂件structDef.h⽂件中：
structDef.h
#include<stdio.h>
#include<stdlib.h>
typedef struct Linknode
{
int val;
struct Linknode* next;
}Linknode;
//创建节点
Linknode*create_link(int val)
{
Linknode* head =(Linknode*)malloc(sizeof(Linknode));
head->val = val;
head->next =NULL;
return head;
}
/
/连接节点
void connection_linknode(Linknode* node1, Linknode* node2)
{
node1->next = node2;
}
//输出单链表
void print_link(Linknode* head)
{
while(head)
{
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
然后写删除重复节点函数DeleteDuplication
//删除有序链表中的重复节点，重复节点⼀个不留
void DeleteDuplication(Linknode** head)
{
if((head ==NULL)||(*head ==NULL))
return;
Linknode* pre =NULL;
Linknode* current =*head;
while(current !=NULL)//current要右移，所以⽤while
{
Linknode* next = current->next;
if((next !=NULL)&&(current->val == next->val))
{
//重复节点是链中节点
int value = current->val;
Linknode* node = current;
while((node !=NULL)&&(node->val == value))
{
next = node->next;
free(node);
node =NULL;
node = next;
}
if(pre ==NULL)//说明头节点已被删除
*head = next;
else//头节点未被删除，令pre指向next，使链表保持连接
pre->next = next;
current = next;
}
else{
pre = current;
current = next;
}
}
}
编写测试函数分别测试删除链中、链头、链尾元素时的情况，并测试链中⽆重复元素和链中全部元素均重复的情况。
void Test1()
{
Linknode* head1 =create_link(1);
Linknode* head2 =create_link(2);
Linknode* head3 =create_link(3);
Linknode* head4 =create_link(3);
c语言struct头文件
Linknode* head5 =create_link(3);
Linknode* head6 =create_link(4);
Linknode* head7 =create_link(4);
Linknode* head8 =create_link(5);
connection_linknode(head1, head2);
connection_linknode(head2, head3);
connection_linknode(head3, head4);
connection_linknode(head4, head5);
connection_linknode(head5, head6);
connection_linknode(head6, head7);
connection_linknode(head7, head8);
printf("建⽴单链表：\n");
print_link(head1); DeleteDuplication(&head1);
printf("删除重复元素(链中)：\n"); print_link(head1);
printf("*****************************\n"); }
void Test2()
{
Linknode* head1 =create_link(1); Linknode* head2 =create_link(1); Linknode* head3 =create_link(1); Linknode* head4 =create_link(3); Linknode* head5 =create_link(3); Linknode* head6 =create_link(4); Linknode* head7 =create_link(4); Linknode* head8 =create_link(5);
connection_linknode(head1, head2); connection_linknode(head2, head3); connection_linknode(head
3, head4); connection_linknode(head4, head5); connection_linknode(head5, head6); connection_linknode(head6, head7); connection_linknode(head7, head8);
printf("建⽴单链表：\n");
print_link(head1); DeleteDuplication(&head1);
printf("删除重复元素(链头)：\n"); print_link(head1);
printf("*****************************\n"); }
void Test3()
{
Linknode* head1 =create_link(1); Linknode* head2 =create_link(2); Linknode* head3 =create_link(3); Linknode* head4 =create_link(3); Linknode* head5 =create_link(3); Linknode* head6 =create_link(4); Linknode* head7 =create_link(4); Linknode* head8 =create_link(4);
connection_linknode(head1, head2); connection_linknode(head2, head3); connection_linknode(head
3, head4); connection_linknode(head4, head5); connection_linknode(head5, head6); connection_linknode(head6, head7); connection_linknode(head7, head8);
printf("建⽴单链表：\n");
print_link(head1); DeleteDuplication(&head1);
printf("删除重复元素(链尾)：\n"); print_link(head1);
printf("*****************************\n");
}
void Test4()
{
Linknode* head1 =create_link(1);
Linknode* head2 =create_link(2);
Linknode* head3 =create_link(3);
Linknode* head4 =create_link(4);
Linknode* head5 =create_link(5);
Linknode* head6 =create_link(6);
Linknode* head7 =create_link(7);
Linknode* head8 =create_link(8);
connection_linknode(head1, head2); connection_linknode(head2, head3); connection_linknode(head3, head4); connection_linknode(head4, head5); connection_linknode(head5, head6); connection_linknode(head6, head7); connection_linknode(head7, head8);
printf("建⽴单链表：\n");
print_link(head1);
DeleteDuplication(&head1);
printf("删除重复元素(⽆重复元素)：\n");
print_link(head1);
printf("*****************************\n");
}
void Test5()
{
Linknode* head1 =create_link(1);
Linknode* head2 =create_link(1);
Linknode* head3 =create_link(3);
Linknode* head4 =create_link(3);
Linknode* head5 =create_link(3);
Linknode* head6 =create_link(4);
Linknode* head7 =create_link(4);
Linknode* head8 =create_link(4);
connection_linknode(head1, head2); connection_linknode(head2, head3); connection_linknode(head3, head4); connection_linknode(head4, head5); connection_linknode(head5, head6); connection_linknode(head6, head7); connection_linknode(head7, head8);
printf("建⽴单链表：\n");
print_link(head1);
DeleteDuplication(&head1);
printf("删除重复元素(全部都是重复元素)：\n"); print_link(head1);
}
主函数调⽤5个测试函数：
int main(void) {
Test1(); Test2(); Test3(); Test4(); Test5();
}
运⾏结果：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。