每天一道剑指offer-删除链表中重复的结点
删除链表中重复的结点
题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
public ListNode deleteDuplication(ListNode pHead){
}解析
此题处理起来棘手的有两个地方：
- 如果某个结点的后继结点与其重复，那么删除该结点的一串连续重复的结点之后如何删除该结点本身，这就要求我们需要保留当前遍历结点的前驱指针。 但是如果从头结点开始就出现一连串的重复呢？我们又如何删除删除头结点，因此我们需要新建一个辅助结点作为头结点的前驱结点。
-
在遍历过程中如何区分当前结点是不重复的结点，还是在删除了它的若干后继结点之后最后也要删除它本身的重复结点？这就需要我们使用一个布尔变量记录是否开启了删除模式（
deleteMode）
经过上述两步分析，我们终于可以安心遍历结点了：
public ListNode deleteDuplication(ListNode pHead){
if(pHead == null){
return null;
}
ListNode node = new ListNode(Integer.MIN_VALUE);
node.next = pHead;
ListNode pre = node, p = pHead;
boolean deletedMode = false;
while(p != null){
if(p.next != null && p.next.val == p.val){
p.next = p.next.next;
deletedMode = true;
}else if(deletedMode){
pre.next = p.next;
p = pre.next;
deletedMode = false;
}else{
pre = p;
p = p.next;
}
}
return node.next;
}出自：http://www.zhenganwen.top
已获授权
END
举报
腾讯云开发者
