[数据结构与算法]BM16 删除有序链表中重复的元素-II

描述

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.

数据范围：链表长度0≤n≤10000，链表中的值满足 ∣val∣≤1000

要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

方法一（删除重复元素后存储，并创建）

时间复杂度o(n)

空间复杂度o(n)

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
       if(head==null) return head;
       Collection<Integer> c=new ArrayList<Integer>();
        ListNode cur=head;
        int tem=1001;  //初始化一个临时变量
        while(cur!=null){
            while(cur!=null&&c.contains(cur.val)){  //如果list列表中有相同的元素
                tem=cur.val;  //暂时存储相同的元素
                cur=cur.next;  //跳过相同的元素，遍历下一个节点
            }
            if(tem!=1001){
                 c.remove(tem); //删除list列表中那个相同的元素
            }
            if(cur!=null&&!c.contains(cur.val)){  //如果当前元素不在列表中，就加入列表中
                c.add(cur.val);
                cur=cur.next;
            }
        }
//         if(c.isEmpty()){  //可要可不要判断一下
//             return null;
//         }
        ListNode ph=new ListNode(0);
        ListNode pr=ph;
        for(Integer d:c){  //创建链表
            ListNode temp=new ListNode(d);
            temp.next=null;
            pr.next=temp;
            pr=pr.next;
        }
        return ph.next;
    }
}

方法二

在链表上遍历，并直接删除重复的元素

时间复杂度o(n)

空间复杂度o(1)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    struct ListNode* dummp = (int) malloc(sizeof(int));
    dummp->next = head;     //空节点插入链表头部
    struct ListNode* p = dummp;
 
    while(p->next && p->next->next){      //每次都是2个节点判断
        if(p->next->val == p->next->next->val){      //存在重复节点
            int num_flag = p->next->val;          //记录第一个重复节点的值
            while(p->next && p->next->val == num_flag)    //循环遍历后续节点的值，并与记录的节点值比较，相同则逐个删除
                p->next = p->next->next;
        }else     //本轮不存在重复节点，值链表指针后移
            p = p->next;
    }
    return dummp->next;    //返回结果
}