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

HQ数字卡

关注

发布于: 2021 年 03 月 25 日

题目

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii

eg:

输入：head = [1,2,3,3,4,4,5]

输出：[1,2,5]

代码


/** * 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 {    /**    * 时间复杂度 O(n)    * 空间复杂度 O(1)    */    public ListNode deleteDuplicates(ListNode head) {        if (head == null) {            return 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){                int tempVal = cur.next.val;                while (cur.next != null && cur.next.val == tempVal) {                    cur.next = cur.next.next;                }            } else {                cur = cur.next;            }        }        return dummy.next;    }}

复制代码

总结

这个题目是链表操作的考察题，链表题目一般题意容易理解，考察代码处理细节。
在题目处理中，我们使用了 dummy 虚拟节点，可以简化 head 的处理。常见的 dummy 使用方法如下

    ListNode dummy = new ListNode(-1);    dummy.next = head;
    // 逻辑处理
    return dummy.next;

复制代码

坚持每日一题，加油！

发布于: 2021 年 03 月 25 日阅读数: 7

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

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

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

题目

代码

总结

HQ数字卡

评论