先定义一个头节点用于指示链表的头部位置,方便最后返回链表。
然后定义两个指针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; }