题目:在一个排序的链表中,如何删除重复的结点?
思路:
设置一个preNode,用于记录当前结点的前一个结点,如果当前结点和后一结点的值相同(记该值为dupVal),通过循环往后找到第一个不为dupVal的结点,把该结点设置为当前结点,并赋值给preNode.next,即相当于完成了删除操作;而当前结点和后一结点的值不相同时,把当前结点和preNode往后移一位即可。
实现:
public ListNode deleteDuplication(ListNode pHead)
{
if (pHead == null || pHead.next == null) return pHead;
ListNode curNode = pHead;
ListNode preNode = null;
while(curNode!=null){
if(curNode.next!=null && curNode.val == curNode.next.val){
ListNode delete = curNode;
int dulpValue = curNode.val;
while(delete!=null && delete.val == dulpValue){
delete = delete.next;
}
if(preNode == null){
pHead = delete;
}else{
preNode.next = delete;
}
curNode = delete;
}else{
preNode = curNode;
curNode = curNode.next;
}
}
return pHead;
}
收获:
- 删除多个结点时,只要把重复结点前一个结点的next指向重复结点的后一个结点;
- 不要把重复结点一个一个删除,先定义一个确定当前结点是否重复,然后按上一句话的方法进行删除即可。
- 注意如果头结点与之后节点重复时,对于preNode的处理