Leetcode 82. Remove Duplicates from Sorted List II

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。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容