先定义一个头节点用于指示链表的头部位置,方便最后返回链表。
然后定义两个指针p和q,初始化时,p先指向头结点,q指向head,开始遍历链表,因为链表是有序的,所以重复元素一定是连续出现的,所以我的策略就是先找出重复的一段子链表,然后一网打尽,具体做法就是:
如果q.next.val != q.val时,就移动p和q;
如果q.next.val == q.val时,就不动p,然后移动q,移动到与当前重复子链表相邻的第一个元素(不与子链表中的元素相等),此时p位于重复子链表的左边相邻位置,q位于右边的相邻位置,将p的next指针指向q即可完成删除。
public ListNode deleteDuplicates (ListNode head) {
// write code here
if (head == null || head.next == null){
return head;
}
ListNode node = new ListNode();
node.next = head;
ListNode p = node;
ListNode q = head;
while (q != null && q.next != null){
if (q.next.val != q.val){
p = q;
q = q.next;
}else {
while (q.next != null && q.val == q.next.val){
q = q.next;
}
q = q.next;
p.next = q;
}
}
return node.next;
}
京公网安备 11010502036488号