【LeetCode】删除排序链表中的重复元素 Java 题解

HQ数字卡

关注

发布于: 2021 年 04 月 16 日

题目

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素只出现一次。

返回同样按升序排列的结果链表。

eg:

输入：head = [1,1,2]

输出：[1,2]

代码

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode deleteDuplicates(ListNode head) {        ListNode dummy = new ListNode(-1);        dummy.next = head;        ListNode cur = dummy;        while (cur.next != null && cur.next.next != null) {            if (cur.next.val == cur.next.next.val) {                cur.next = cur.next.next;            } else {                cur = cur.next;            }        }        return dummy.next;    }}

复制代码

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode deleteDuplicates(ListNode head) {        if (head == null || head.next == null) {            return head;        }        ListNode slow = head, fast = head;        while (fast != null) {            if (slow.val != fast.val) {                slow.next = fast;                slow = slow.next;            }            fast = fast.next;        }        slow.next = null;        return head;    }}

复制代码

总结

方法一使用了虚拟节点 dummy，简化处理。
方法二采用了快慢指针的思想，执行效率更高！
两种算法的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持每日一题，加油！

发布于: 2021 年 04 月 16 日阅读数: 7

原文链接:【http://xie.infoq.cn/article/140931a90b721908d43b267b3】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】删除排序链表中的重复元素 Java 题解

题目

代码

总结

HQ数字卡

评论