Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
题意:83题的followup,这次重复的元素一个都不保留了。
思路:问题的关键是如果判断一个元素是不是非重复元素,判断的条件就是它不和前面的元素相等也不和后面的元素相等。由于是链表,我们需要用一个变量记录前面的listnode,才能判断。还有一点需要注意的就是头尾节点是没有pre和next的,注意pre和next是否是null的判断。
所以本题需要三个指针,dummy指向已连接起来的符合条件的节点,cur指向当前遍历到的节点,pre指向cur前面一个节点,每遍历到一个节点,如果它和前后都不相等,就把dummy.next指向它,然后把dummy更新为dummy.next。
public ListNode deleteDuplicates(ListNode head) {
ListNode res = new ListNode(0);
if (head == null || head.next == null) {
return head;
}
ListNode dummy = res;
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
if ((pre != null && cur.next != null && cur.val != pre.val && cur.val != cur.next.val)
|| (pre == null && cur.next != null && cur.val != cur.next.val)
|| (cur.next == null && cur.val != pre.val)) {
dummy.next = cur;
dummy = dummy.next;
}
pre = cur;
cur = cur.next;
}
dummy.next = null;
return res.next;
}
bug:最后又疏忽了要把dummy.next指向null,不然1,2,3,3这种case就会fail。