本文主要是介绍剑指offer：删除该链表中重复的结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
思路：
设置三个指针，pre，curr，next。curr代表当前节点，pre代表前一节点，next代表后一节点，思路是每次如果next与curr的值相等，就将next后移直到next指向第一个与curr值不相等的节点，直接令pre->next=next，这样就将curr到next之间重复发节点全部删除了。重点是要特别注意删除头结点的情况。
初始时curr指向头结点，next指向下一节点，如果next和curr的值不相等，就令pre=curr，curr=pre->next。如果next和curr的值相等，就将next往后移一位，一直到next的值与curr的值不相等。此时如果curr是头结点，就重新设置头结点为next指向的节点，curr=next；如果不是头结点，就令pre->next=next，curr=pre->next。
特别注意：
在一切有->next操作的地方都要先确保当前节点不为空。
在判断相等的时候，不能直接判断节点，而是判断value，因为next指针不同。
参考代码：
在线测试
https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&tqId=11209&rp=3&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=3
AC代码
/*
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;ListNode* curr=pHead;ListNode* pnext;ListNode* pre;while(curr!=NULL){pnext=curr->next;if(pnext!=NULL&&pnext->val==curr->val){pnext=pnext->next;while(pnext!=NULL&&pnext->val==curr->val){pnext=pnext->next;}if(curr==pHead)pHead=pnext;elsepre->next=pnext;curr=pnext;}else{pre=curr;curr=pre->next;}}return pHead;}
};
越界？特别注意在一切有->next操作的地方都要先确保当前节点不为空。修改之后还是不对，因为pHead重复的情况应该放在循环里面处理，不应该只单独处理一次。会出现测试用例:{1,1,2,2,3,3,4,4}
/*
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;ListNode* curr=pHead;ListNode* pnext=pHead->next;if(pnext->val==curr->val){while(pnext!=NULL && pnext->val==curr->val){pnext=pnext->next;}pHead=pnext;}if(pHead==NULL||pHead->next==NULL)return pHead;ListNode* pre=pHead;curr=pre->next;while(curr!=NULL&&curr->next!=NULL){pnext=curr->next;if(pnext->val==curr->val){//pnext=pnext->next;while(pnext!=NULL&&pnext->val==curr->val){pnext=pnext->next;}pre->next=pnext;}elsepre=curr;curr=pre->next;}return pHead;}
};之前理解错题意，以为将有重复的元素还保留下来，输出1->2->3->4->5。代码如下：要特别注意如果pNode=NULL，就不能再做->next的操作了，不然会越界报错，所以while里面除了有两个越界检查条件。
/*
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;ListNode* pNode=pHead;while(pNode!=NULL&&pNode->next!=NULL){while(pNode!=NULL&&pNode->next!=NULL&&pNode->next->val==pNode->val){ListNode* temp=pNode->next;pNode->next=temp->next;}pNode=pNode->next;}return pHead;}
};上面两个AC版本分别对应leetcode82和83
leetcode 82 AC代码如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if(head==NULL||head->next==NULL)return head;ListNode* pre=NULL;ListNode* curr=head;ListNode* pnext=NULL;while(curr!=NULL){pnext=curr->next;if(pnext!=NULL&&pnext->val==curr->val){while(pnext!=NULL&&pnext->val==curr->val){pnext=pnext->next;}if(curr==head){head=pnext;curr=pnext;}else{pre->next=pnext;curr=pnext;}}else{pre=curr;curr=pnext;}}return head;}
};
这篇关于剑指offer：删除该链表中重复的结点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
