双指针算法
设两个指针p,q
p指向相同元素区间的前一个节点,q指向相同元素区间的后一个节点;
q会遍历所有节点,用于找到重复区间,p用来删除重复节点和找到下一个节点
最后看p,q指针之间有几个元素,如果有一个,说明不用删除元素了,p = p.next;
如果有多个元素,说明就有重复元素,就需要删除操作,p.next = q;
问题
问题1:为什么需要设立一个虚拟节点dummy
为了避免边界情况:如果一开头就有重复元素,把开头的所有元素删掉,p指针就不知道放在那了
java代码
class Solution {
public ListNode deleteDuplication(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode p = dummy; //上一段的节点
while(p.next != null)
{
ListNode q = p.next; //下一段的第一个节点
while(q != null && p.next.val == q.val) q = q.next;
if(p.next.next == q) p = p.next; //如果p和q之间的长度为1
else p.next = q;
}
return dummy.next;
}
}