首页 >
删除单链表中的重复节点(c语言版本)
删除单链表中的重复节点(c语言版本)
这是一道经典的面试题，下面是我的研究和举一反三，特整理如下：
分为三种情形:
（1）删除有序链表的重复节点，重复节点一个都不留
（2）删除有序链表的重复节点，重复节点只留一个
（3）删除无序链表的重复节点，重复节点只留一个
下面是相关节点的定义：
typedef struct ListNode {int val;struct ListNode *next;
} ListNode;ListNode* CreateListNode(int value){ListNode* pNode = (ListNode*)malloc(sizeof(ListNode));if(pNode == NULL){printf("failed to create ListNode
");exit(-1);} pNode->val = value;pNode->next = NULL;return pNode;
} void ConnectListNodes(ListNode* pCurrent, ListNode* pNext){if(pCurrent == NULL || pNext == NULL){printf("Error to connect two nodes
");exit(-1);} pCurrent->next = pNext;
} void DestroyListNode(ListNode* pNode){if(pNode != NULL){printf("-----delete list node [%d]-----
", pNode->val);free(pNode);}
}下面给出解读：
1）下面的代码针对删除有序单链表的重复节点，重复节点都删除。
ListNode* DeleteDuplication(ListNode* pHead){if(pHead == NULL)return NULL;//指向当前节点前最晚访问过的不重复节点； ListNode* pPre = NULL;//指向当前正在处理的节点；ListNode* pCur = pHead;//指向当前节点后面的值相同的节点；ListNode* pNext = NULL;//临时存放节点ListNode* pNode = NULL;while(pCur != NULL){//下一个节点与当前节点相同if(pCur->next != NULL && pCur->next->val == pCur->val){pNext = pCur->next;//找出所有与当前节点值相同的节点，因为是排序过的链表，它们都在一切while(pNext != NULL && pNext->val == pCur->val){pNode = pNext->next;DestroyListNode(pNext);pNext = pNode;} //现在要删除pCur->...->pNext->之间的所有节点//如果pCur是链表头，要更新链表头的位置if(pCur == pHead)pHead = pNext;elsepPre->next = pNext;DestroyListNode(pCur);pCur = pNext;}else{pPre = pCur;pCur = pCur->next;} } return pHead;
}2）下面是有序链表，只留一个的
//删除有序链表中的重复节点，仅保留一个，使用2指针定位
//考虑到这里需要用到测试框架，这里必须使用二级指针
ListNode* DeleteDuplication(ListNode** pHead){if(pHead == NULL || *pHead == NULL) return NULL;//指向当前正在处理的节点；ListNode* pCur = *pHead;//指向当前节点后面的值相同的节点；ListNode* pNext = NULL;//临时存放节点ListNode* pNode = NULL;while(pCur != NULL){//下一个节点与当前节点相同if(pCur->next != NULL && pCur->next->val == pCur->val){pNext = pCur->next;//找出所有与当前节点值相同的节点，因为是排序过的链表，它们都在一切while(pNext != NULL && pNext->val == pCur->val){pNode = pNext->next;DestroyListNode(pNext);pNext = pNode;} //将当前节点指向后续不同值的首个节点pCur->next = pNext;} pCur = pCur->next;} return *pHead;
} 3）下面是无序链表，只留一个的(注意：这里会兼容前面的两种情况)
//删除无序链表中的重复节点，仅保留一个，使用2指针定位
//考虑到这里需要用到测试框架，这里必须使用二级指针
ListNode* DeleteDuplication(ListNode** pHead){if(pHead == NULL || *pHead == NULL)return NULL; //指向当前正在处理的节点；ListNode* p = *pHead;//用于遍历p之后的节点；ListNode* q = NULL;ListNode* r = NULL;while(p != NULL){q = p; //若后面有节点与当前节点相同，将其统统删除while(q->next != NULL){if(q->next->val == p->val){//保存需要删掉的节点r = q->next;//需要删掉的节点的前后节点相接q->next = r->next;DestroyListNode(r);} else{ q = q->next;} } p = p->next; } return *pHead;
}下面是针对第三种情况编写的用户测试的截图：
下面是我针对第三种情况的源码实现：
//description: 描述删除单链表的重复节点
//date: 2019-03-20#include
#include
#include typedef struct ListNode {int val;struct ListNode *next;
} ListNode;ListNode* CreateListNode(int value){ListNode* pNode = (ListNode*)malloc(sizeof(ListNode));if(pNode == NULL){printf("failed to create ListNode
");exit(-1);}pNode->val = value;pNode->next = NULL;return pNode;
}void ConnectListNodes(ListNode* pCurrent, ListNode* pNext){if(pCurrent == NULL || pNext == NULL){printf("No necessary to connect two nodes
");return;}pCurrent->next = pNext;
}void DestroyListNode(ListNode* pNode){if(pNode != NULL){printf("-----delete list node [%d]-----
", pNode->val);free(pNode);}
}//在表头节点后面拼接n个随机元素的单链表
void CreateList(ListNode **pHead, int n){if(pHead == NULL || *pHead == NULL){printf("Invalid List header ptr
");exit(-1);}int i;srand(time(0));ListNode *pNew, *pNode = *pHead;for(i=0; ival = rand()%100 + 1;pNode->next = pNew;pNode = pNew;}pNode->next = NULL;
}void DestroyList(ListNode* pHead){ListNode *pNode = pHead;while(pNode != NULL){pHead = pNode->next;free(pNode);pNode = pHead;}
}void PrintList(ListNode* pHead){printf("------------print list begin-----------");ListNode* pNode = pHead;while(pNode != NULL){printf("%d ", pNode->val);pNode = pNode->next;}printf("------------print list end-------------");
}//==================业务函数定义到这里=============//删除无序链表中的重复节点，仅保留一个，使用2指针定位
//考虑到这里需要用到测试框架，这里必须使用二级指针
ListNode* DeleteDuplication(ListNode** pHead){if(pHead == NULL || *pHead == NULL)return NULL;//指向当前正在处理的节点；ListNode* p = *pHead;//用于遍历p之后的节点；ListNode* q = NULL;ListNode* r = NULL;while(p != NULL){q = p;//若后面有节点与当前节点相同，将其统统删除while(q->next != NULL){if(q->next->val == p->val){//保存需要删掉的节点r = q->next;//需要删掉的节点的前后节点相接q->next = r->next;DestroyListNode(r);}else{q = q->next;}}p = p->next;}return *pHead;
}//==================测试代码=======================
void Test(char* testName, ListNode** pHead, int* expectedValues, int expectedLength){if(testName != NULL)printf("%s begins:
", testName);//======真正要干的活儿==========ListNode* pNode = DeleteDuplication(pHead);int idx = 0;while(pNode !=NULL && idx < expectedLength){if(pNode->val != expectedValues[idx])break;pNode = pNode->next;idx++;}if(pNode == NULL && idx == expectedLength)printf("%s Passed.
", testName);elseprintf("%s FAILED.
", testName);
}//--------------下面测试一些特例情况--------------//某些节点是重复的
void Test1(){//构建一个单链表ListNode* pNode1 = CreateListNode(1);ListNode* pNode2 = CreateListNode(2);ListNode* pNode3 = CreateListNode(3);ListNode* pNode4 = CreateListNode(3);ListNode* pNode5 = CreateListNode(4);ListNode* pNode6 = CreateListNode(4);ListNode* pNode7 = CreateListNode(5);ConnectListNodes(pNode1, pNode2);ConnectListNodes(pNode2, pNode3);ConnectListNodes(pNode3, pNode4);ConnectListNodes(pNode4, pNode5);ConnectListNodes(pNode5, pNode6);ConnectListNodes(pNode6, pNode7);ListNode* pHead = pNode1;int expectedValues[] = {1, 2, 3, 4, 5};Test("Test1", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));//删除该单链表DestroyList(pHead);
}//没有节点重复
void Test2(){//构建一个单链表ListNode* pNode1 = CreateListNode(1);ListNode* pNode2 = CreateListNode(2);ListNode* pNode3 = CreateListNode(3);ListNode* pNode4 = CreateListNode(4);ListNode* pNode5 = CreateListNode(5);ListNode* pNode6 = CreateListNode(6);ListNode* pNode7 = CreateListNode(7);ConnectListNodes(pNode1, pNode2);ConnectListNodes(pNode2, pNode3);ConnectListNodes(pNode3, pNode4);ConnectListNodes(pNode4, pNode5);ConnectListNodes(pNode5, pNode6);ConnectListNodes(pNode6, pNode7);ListNode* pHead = pNode1;int expectedValues[] = {1, 2, 3, 4, 5, 6, 7};Test("Test2", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));//删除该单链表DestroyList(pHead);
}//除了一个节点之外其它所有节点的值都相同
void Test3(){//构建一个单链表ListNode* pNode1 = CreateListNode(1);ListNode* pNode2 = CreateListNode(1);ListNode* pNode3 = CreateListNode(1);ListNode* pNode4 = CreateListNode(1);ListNode* pNode5 = CreateListNode(1);ListNode* pNode6 = CreateListNode(1);ListNode* pNode7 = CreateListNode(2);ConnectListNodes(pNode1, pNode2);ConnectListNodes(pNode2, pNode3);ConnectListNodes(pNode3, pNode4);ConnectListNodes(pNode4, pNode5);ConnectListNodes(pNode5, pNode6);ConnectListNodes(pNode6, pNode7);ListNode* pHead = pNode1;int expectedValues[] = {1, 2};Test("Test3", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));//删除该单链表DestroyList(pHead);
}//所有节点的值都是相同的
void Test4(){//构建一个单链表ListNode* pNode1 = CreateListNode(1);ListNode* pNode2 = CreateListNode(1);ListNode* pNode3 = CreateListNode(1);ListNode* pNode4 = CreateListNode(1);ListNode* pNode5 = CreateListNode(1);ListNode* pNode6 = CreateListNode(1);ListNode* pNode7 = CreateListNode(1);ConnectListNodes(pNode1, pNode2);ConnectListNodes(pNode2, pNode3);ConnectListNodes(pNode3, pNode4);ConnectListNodes(pNode4, pNode5);ConnectListNodes(pNode5, pNode6);ConnectListNodes(pNode6, pNode7);ListNode* pHead = pNode1;int expectedValues[] = {1};Test("Test4", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));//删除该单链表DestroyList(pHead);
}//所有节点都成对出现
void Test5(){//构建一个单链表ListNode* pNode1 = CreateListNode(1);ListNode* pNode2 = CreateListNode(1);ListNode* pNode3 = CreateListNode(2);ListNode* pNode4 = CreateListNode(2);ListNode* pNode5 = CreateListNode(3);ListNode* pNode6 = CreateListNode(3);ListNode* pNode7 = CreateListNode(4);ListNode* pNode8 = CreateListNode(4);ConnectListNodes(pNode1, pNode2);ConnectListNodes(pNode2, pNode3);ConnectListNodes(pNode3, pNode4);ConnectListNodes(pNode4, pNode5);ConnectListNodes(pNode5, pNode6);ConnectListNodes(pNode6, pNode7);ConnectListNodes(pNode7, pNode8);ListNode* pHead = pNode1;int expectedValues[] = {1, 2, 3, 4};Test("Test5", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));//删除该单链表DestroyList(pHead);
}//除了两个节点之外其它所有节点都成对出现
void Test6(){//构建一个单链表ListNode* pNode1 = CreateListNode(1);ListNode* pNode2 = CreateListNode(1);ListNode* pNode3 = CreateListNode(2);ListNode* pNode4 = CreateListNode(3);ListNode* pNode5 = CreateListNode(3);ListNode* pNode6 = CreateListNode(4);ListNode* pNode7 = CreateListNode(5);ListNode* pNode8 = CreateListNode(5);ConnectListNodes(pNode1, pNode2);ConnectListNodes(pNode2, pNode3);ConnectListNodes(pNode3, pNode4);ConnectListNodes(pNode4, pNode5);ConnectListNodes(pNode5, pNode6);ConnectListNodes(pNode6, pNode7);ConnectListNodes(pNode7, pNode8);ListNode* pHead = pNode1;int expectedValues[] = {1, 2, 3, 4, 5};Test("Test6", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));//删除该单链表DestroyList(pHead);
}//链表中只有两个不重复的节点
void Test7(){//构建一个单链表ListNode* pNode1 = CreateListNode(1);ListNode* pNode2 = CreateListNode(2);ConnectListNodes(pNode1, pNode2);ListNode* pHead = pNode1;int expectedValues[] = {1, 2};Test("Test7", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));//删除该单链表DestroyList(pHead);
}//链表中只有两个重复的节点
void Test8(){//构建一个单链表ListNode* pNode1 = CreateListNode(1);ListNode* pNode2 = CreateListNode(1);ConnectListNodes(pNode1, pNode2);ListNode* pHead = pNode1;int expectedValues[] = {1};Test("Test8", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));//删除该单链表DestroyList(pHead);
}//无序链表中某些节点是重复的
void Test9(){//构建一个单链表ListNode* pNode1 = CreateListNode(11);ListNode* pNode2 = CreateListNode(2);ListNode* pNode3 = CreateListNode(3);ListNode* pNode4 = CreateListNode(3);ListNode* pNode5 = CreateListNode(9);ListNode* pNode6 = CreateListNode(4);ListNode* pNode7 = CreateListNode(5);ListNode* pNode8 = CreateListNode(5);ListNode* pNode9 = CreateListNode(3);ConnectListNodes(pNode1, pNode2);ConnectListNodes(pNode2, pNode3);ConnectListNodes(pNode3, pNode4);ConnectListNodes(pNode4, pNode5);ConnectListNodes(pNode5, pNode6);ConnectListNodes(pNode6, pNode7);ConnectListNodes(pNode7, pNode8);ConnectListNodes(pNode8, pNode9);ListNode* pHead = pNode1;int expectedValues[] = {11, 2, 3, 9, 4, 5};Test("Test9", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));//删除该单链表DestroyList(pHead);
}//链表中只有一个节点
void Test10(){//构建一个单链表ListNode* pNode1 = CreateListNode(1);ConnectListNodes(pNode1, NULL);ListNode* pHead = pNode1;int expectedValues[] = {1};Test("Test10", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));//删除该单链表DestroyList(pHead);
}//空链表
void Test11(){ListNode* pHead = NULL;Test("Test11", &pHead, NULL, 0);
}int main(int argc, char** argv){Test1();Test2();Test3();Test4();Test5();Test6();Test7();Test8();Test9();Test10();Test11();return 0;
} 参考文献
[1].《剑指Offer名企面试官精讲典型编程题》第2版 面试题18-2
更多相关：
-
题目：链表中倒数第k个节点 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。 示例： 给定一个链表: 1->2->3->4->5, 和 k =...
-
题目：从尾到头打印链表 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 示例 1： 输入：head = [1,3,2] 输出：[2,3,1] 限制： 0 <= 链表长度 <= 10000 题目： /*** Definition for singly-linked list.* struct Lis...
-
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 解法一：双指针法 时间复杂度：O(a+b) 循环比较两个子问题的次数为 a+b a,b为两个子问题的长度空间复杂度：O(1) 双指针，常数级别复杂度...
-
下面是后面链表相关题目中需要用到的链表结点的定义和相关操作函数，参见下面的list.h文件： 注意链表结点的定义采用cpp的定义方式，它会被cpp的文件调用。比如后面删除链表重复结点的文件del_repeated_list.cpp中的编译方式： g++ -g del_repeated_list.cpp -o del_repeate...
-
当一个IT组织开始走到需要实施网络边缘的旅程时，他们很快意识到面对的挑战与他们在传统数据中心内所经历的挑战不同。 第一个挑战是空间。与更大的核心或区域数据中心同类产品相比，许多边缘站点的物理尺寸更小，因此，需要仔细计划好，尝试在未为其专门设计的空间中安装硬件。 第二个挑战是运行环境。还必须解决的可能面对的冷热温度变化 ，天气，无...
-
单向循环链表单链表的一个变形是单向循环链表, 链表的最后一个节点的next域不再为None, 而是指向链表的头节点.单向循环链表如图所示:单向循环链表同样单向循环链表也是要使用python来对它的基本功能进行一个封装. 总体大致的功能如下:is_empty() 判断链表是否为空length() 返回链表的长度travel() 遍历ad...
-
题目： 二叉搜索树与双向链表 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 为了让您更好地理解问题，以下面的二叉搜索树为例： 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一...
-
题目：删除链表的节点 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。 返回删除后的链表的头节点。 注意：此题对比原题有改动 示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为...
-
【从零开始的ROS四轴机械臂控制】（一）- 实际模型制作、Solidworks文件转urdf与rviz仿真 一、模型制作 1.实际模型制作 2.Solidworks模型制作 二、Solidworks文件转urdf 1.sw_urdf_exporter插件 2.添加坐标系和转轴 3.导出urdf文件 三、rivz仿真...