美文网首页
LeetCode_82 删除排序链表中的重复元素II(链表题)

LeetCode_82 删除排序链表中的重复元素II(链表题)

作者: monkey01 | 来源:发表于2018-11-05 18:15 被阅读18次

    题目地址:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

    题目:

    给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

    示例 1:

    输入: 1->2->3->3->4->4->5
    输出: 1->2->5
    

    试题分析:

    该题核心的思路是扫描到节点后内部嵌套一个循环继续往后遍历,因为链表是有序的,所以遍历到节点值不相等即可停止修改链表连接,一次性将中间重复的元素删除就完成了重复元素的删除,整个的时间复杂度为O(n),虽然在外循环内部嵌套了一个循环,但是因为链表是有序的,内部不会出现再次重复循环。因为可能会对头节点有删除操作,所以新建了空头节点,并记录删除节点前置指针用于删除重复节点使用。

    代码:

    public ListNode deleteDuplicates(ListNode head) {
            ListNode newHead = new ListNode(-1);
            newHead.next = head;
            ListNode pre = newHead;
            if(head==null || head.next==null){
                return head;
            }
    
            ListNode cur = head;
            while(cur!=null){
                boolean duplicate = false;
    
                while(cur.next!=null && cur.val==cur.next.val) {
                    //对重复数字进行循环删除
                    duplicate = true;
                    cur = cur.next;
                }
                //删除最后一个重复节点
                if(duplicate){
                    pre.next = cur.next;
                }else {
                    pre.next = cur;
                    pre = cur;
                }
                cur = cur.next;
            }
            return newHead.next;
        }
    

    源码路径:com.monkey01.linkedlist.RemoveDuplicatesFromSortedListII_82

    配套测试代码路径:test目录com.monkey01.linkedlist.RemoveDuplicatesFromSortedListII_82Test

    https://github.com/feiweiwei/LeetCode4Java.git

    相关文章

      网友评论

          本文标题:LeetCode_82 删除排序链表中的重复元素II(链表题)

          本文链接:https://www.haomeiwen.com/subject/vpxexqtx.html