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

目录

剑指offer-56删除链表中重复的结点目录 1题目描述2题目答案

1题目描述

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

2题目答案

递归

class Solution { public: ListNode* deleteDuplication(ListNode* pHead){ if (pHead==NULL) return NULL; if (pHead!=NULL && pHead->next==NULL) return pHead; ListNode* current; //设置一个当前节点 //下一个节点的值，等于现在节点的值 if ( pHead->next->val==pHead->val){ current=pHead->next->next; //跨过两个重复的值 while (current != NULL && current->val==pHead->val) //如果跨过后的值与头节点的值相等 current=current->next; //说明有三个及以上重复的情况，再向下取 return deleteDuplication(current); } //下一个节点的值，不等于现在节点的值 else { current=pHead->next; //当前节点向下取 pHead->next=deleteDuplication(current); //下一节点接在被删除后的节点 return pHead; //头节点的值与下一节点的值不同，则不重复，返回该头节点 } } };

也是递归

class Solution { public: ListNode* deleteDuplication(ListNode* pHead){ if(pHead==NULL ||pHead->next==NULL) return pHead; if(pHead->val == pHead->next->val){ // 当前结点是重复结点 ListNode* p = pHead->next; while(p!=NULL && p->val==pHead->val) // 跳过值与当前结点相同的全部结点,找到第一个与当前结点不同的结点 p = p->next; return deleteDuplication(p); // 从第一个与当前结点不同的结点开始递归 } else{ // 当前结点不是重复结点 pHead->next = deleteDuplication(pHead->next); // 保留当前结点，从下一个结点开始递归 return pHead; } } };