1. 首页
  2. Leetcode经典148题

leetCode-83-Remove-Duplicates-from-Sorted-List

题目描述(简单难度)

leetCode-83-Remove-Duplicates-from-Sorted-List

给定一个链表,去重,每个数字只保留一个。

解法一 修改

按偷懒的方法,直接在 public ListNode deleteDuplicates(ListNode head) { ListNode pre = new ListNode(0); ListNode dummy = pre; pre.next = head; ListNode cur = head; while(cur!=null && cur.next!=null){ boolean equal = false; while(cur.next!=null && cur.val == cur.next.val){ cur = cur.next; equal = true; } if(equal){ /*************修改的地方*****************/ //pre.next 指向 cur,不再跳过当前数字 pre.next = cur; pre = cur; /**************************************/ equal = false; }else{ pre = cur; } cur = cur.next; } return dummy.next; }

递归

public ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;
    //如果头结点和后边的节点相等
    if (head.next != null && head.val == head.next.val) {
        //跳过所有重复数字
        while (head.next != null && head.val == head.next.val) {
            head = head.next;
        } 
        /*************修改的地方*****************/
        //将 head 也包含,进入递归
        return deleteDuplicates(head);
        /**************************************/
        //头结点和后边的节点不相等
    } else {
        //保留头结点,后边的所有节点进入递归
        head.next = deleteDuplicates(head.next);
    }
    //返回头结点
    return head;
}

解法二 迭代

public ListNode deleteDuplicates(ListNode head) { ListNode cur = head; while(cur!=null && cur.next!=null){ //相等的话就删除下一个节点 if(cur.val == cur.next.val){ cur.next = cur.next.next; //不相等就后移 }else{ cur = cur.next; } } return head; }

时间复杂度:O(n)。

空间复杂度:O(1)。

解法三 递归

同样的,递归也会更简单些。

public ListNode deleteDuplicates(ListNode head) { 
    if(head == null || head.next == null){
        return head;
    }
    //头结点和后一个时候相等
    if(head.val == head.next.val){
        //去掉头结点
        return deleteDuplicates(head.next);
    }else{
        //加上头结点
        head.next = deleteDuplicates(head.next);
        return head;
    }
}

如果

阅读全文

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程
  4. JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

    本文著作权归作者所有,如若转载,请注明出处

    转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

    标题:leetCode-83-Remove-Duplicates-from-Sorted-List

    链接:https://www.javajike.com/article/3219.html

« leetCode-82-Remove-Duplicates-from-Sorted-ListII
leetCode-84-Largest-Rectangle-in-Histogram»

相关推荐

QR code