剑指offer 删除链表中重复的结点

男娘i 2021-11-06 00:20 281阅读 0赞

# [剑指offer题型分类及各题的代码及解题思路][offer] #

## 题目描述 ##

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

**分析：**

1. 首先添加一个头节点，以方便碰到第一个和第二个节点就相同的情况。

2.设置 pre ，cur 指针， pre指针指向当前确定不重复的那个节点，而cur指针相当于工作指针，一直往后面搜索。

**C++实现代码如下：**

ListNode* deleteDuplication(ListNode* pHead)
    {
    	//1、若头指针为空或只有一个结点，则不可能有重复的，直接返回头结点
    	if(pHead == NULL || pHead->next == NULL)
    		return pHead;
    	//2、创建一个新的头结点，防止头结点重复
    	ListNode* Head = new ListNode(0);
    	Head->next = pHead;    //新的头结点
    	ListNode* pre = Head;    //pre为判断结点的前驱
    	ListNode* cur = Head->next;    //cur和cur->next为要判断的结点
    	//3、若有重复的结点，则删除；若无，则pre和cur往后移动，继续寻找，直至找到尾结点
    	while(cur != NULL)
    	{
    		if(cur->next != NULL && cur->val == cur->next->val)
    		{
    			//假如有多个连续的数据相同的结点，找到最后一个结点位置
    			while(cur->next != NULL && cur->val == cur->next->val)
    				cur = cur->next;
    			
    			pre->next = cur->next;
    			cur = cur->next;
    		}
    		else
    		{
    			pre = pre->next;
    			cur = cur->next;
    		}
    	}
    	return Head->next;
    }

[offer]: https://blog.csdn.net/qq_26079093/article/details/96605538