删除链表中重复的节点

青旅半醒 2022-04-24 07:04 273阅读 0赞

## 删除节点 ##

*  链表中的增删是最常见的问题，那么我们如何在一个完整的链表中删除重复的节点呢？

例如：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

遇到链表的问题别慌，相信自己只要你能想得通就能写的出来，而最好的办法莫过于画图，上次我就提到过画图对于我们解决问题那可是至关重要的，在这里我就不画图了，因为还是有点麻烦的，对于这道题，相对而言，还是比较容易的。

*  解题思路  
    1、既然已经排好序，那么只需要判断相邻元素是否重复即可。  
    2、这时就要考虑头结点如果被删除了该怎么办，所以应该将头结点保存一下。  
    3、然后遍历连链表，删除重复节点。完成链表的删除
 *  具体实现如下

#include<iostream>
    using namespace std;
    
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    		val(x), next(NULL) {
    	}
    };
    
    //在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，
    //重复的结点不保留，返回链表头指针。
    //例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
    ListNode* deleteDuplication(ListNode* pHead){
    	if (pHead == NULL || pHead->next == NULL) return pHead;
    	else
    	{
    		//新建一个节点，防止头结点要被删除
    		ListNode* newHead = (ListNode*)malloc(sizeof(ListNode));
    		newHead->next = pHead;
    		ListNode* pre = newHead;
    		ListNode* p = pHead;
    		ListNode* next = NULL;
    		while (p != NULL && p->next != NULL)
    		{
    			next = p->next;
    			if (p->val == next->val)//如果当前节点的值和下一个节点的值相等
    			{
    				while (next != NULL && next->val == p->val)//向后重复查找
    					next = next->next;
    				pre->next = next;//指针赋值，就相当于删除
    				p = next;
    			}
    			else//如果当前节点和下一个节点值不等，则向后移动一位
    			{
    				pre = p;
    				p = p->next;
    			}
    		}
    		return newHead->next;//返回头结点的下一个节点
    	}
    }
    
    //创建节点
    ListNode* CreateListNode(int val) {
    	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    	node->val = val;
    	node->next = NULL;
    	return node;
    }
    //打印节点
    void Print(ListNode* head) {
    	ListNode* cur = head;
    	while (cur->next != NULL) {
    		printf("%p(%d) --> ", cur, cur->val);
    		cur = cur->next;
    	}
    	printf("%p(%d) --> NULL",cur, cur->val);
    	printf("\n");
    }
    
    int main(){
    	ListNode* node1 = CreateListNode(1);
    	ListNode* node2 = CreateListNode(2);
    	ListNode* node3 = CreateListNode(3);
    	ListNode* node4 = CreateListNode(3); 
    	ListNode* node5 = CreateListNode(4);
    	ListNode* node6 = CreateListNode(4);
    	ListNode* node7 = CreateListNode(5);
    	node1->next = node2; node2->next = node3;
    	node3->next = node4; node4->next = node5;
    	node5->next = node6; node6->next = node7;
    	Print(node1);
    	deleteDuplication(node1);
    	Print(node1);
    	system("pause");
    	return 0;
    }

其实代码看起来并不是很复杂，只要你能将这个过程想明白，然后一步步的按照这个过程往下走，那实现这个功能便没有那么复杂，在这里我还是要强调一下，像这种删除链表中的节点，一定要记着保存它的后序元素，否则如果删除了这个节点，那么它的后序节点就都会丢失。这种思路是按照常规思路，如果你还有更好的方法记得分享给我哦！