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

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

思路 找到重复的就删除

C++实现（待优化）

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* deleteDuplication(ListNode* pHead) { if(pHead==NULL || pHead->next==NULL) return pHead; //如果节点数目少于2个，直接返回 ListNode *cur = pHead->next; if(pHead->val == cur->val){ //若首节点pHead就重复了，就寻找到下一个不重复的节点作为首节点.！！这里可以优化！！ while(pHead->val == cur->val){ cur = cur->next; if(cur==NULL) return NULL; } pHead = cur; cur = cur->next; return deleteDuplication(pHead); } ListNode *last = pHead; //记录上一个不重复的节点 while(cur!=NULL && cur->next!=NULL){ if(cur->val != cur->next->val){ // 若当前节点与下一节点不重复，则last指向当前节点 last->next = cur; last = cur; cur = cur->next; } else{ // 若当前节点与下一节点重复了，则找到下一个不重复的节点 int pre = cur->val; while(pre == cur->val){ cur = cur->next; if(cur==NULL) break; } } } last->next = cur; return pHead; } }; 总结 通过程序后，去看别人优秀的代码，发现还有不少可以优化的地方，比如，可以先自己设一个ListNode* pre，然后pre->next指向pHead即可，这样的话，就可以去掉上面说的可以优化的地方了，将其直接与下面的while合在一起处理，最后返回pre->next即可。从而使得代码更为简介与高效。反思 通过这次编程实现，我发现了自己对之前学过的链表知识又忘记了…本来挺简单的一道题，但由于对链表的不熟悉，还是做了蛮久的。而且，这道题也有一些细节需要注意，从而实现优化。希望自己能记住这次编程实现学到的知识，不要又忘记了。。。

题目链接 牛客网编程题——剑指offer：删除链表中重复的结点