cpp 解法, 执行用时: 276 ms, 内存消耗: 135.4 MB, 提交时间: 2023-10-17 15:21:08

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* deleteDuplicatesUnsorted(ListNode* head) {
        if (head->next == nullptr) return head;

        // 边缘强开的考虑
        ListNode* dummy = new ListNode(0);
        dummy->next = head;

        // 找到重复元素，因为不能保留重复的元素，所以要先遍历然后直接删除
        int val2cnt[100001];
        memset(val2cnt, 0, sizeof(val2cnt));

        // 当前点
        ListNode* pos = head;
        while (pos != nullptr) {
            val2cnt[pos->val]++;
            pos = pos->next;
        }

        // 上一个结点
        ListNode* pre = dummy;
        pos = head;
        while (pos != nullptr) {
            if (val2cnt[pos->val] > 1) {
                pre->next = pos->next;
            } else {
                pre = pre->next;
            }
            pos = pos->next;
        }
        return dummy->next;
    }
};

java 解法, 执行用时: 60 ms, 内存消耗: 62 MB, 提交时间: 2023-10-17 15:19:34

/**
 * 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 deleteDuplicatesUnsorted(ListNode head) {
        if(head==null||head.next==null) return head;
        Map<Integer, Integer> map = new HashMap<>();
        ListNode header = new ListNode(-1);
        header.next = head;

        int maxCount = 1;

        ListNode p = header;
        while(p.next!=null){
            if(!map.containsKey(p.next.val)){
                map.put(p.next.val, 1);
                p = p.next;
            }else{
                map.put(p.next.val, map.get(p.next.val)+1);
                //优化一：如果第一次遍历就已经发现重复节点，当即就可以直接删除，避免第二次遍历再花时间
                p.next = p.next.next;
                maxCount++;
            }
        }
        //优化二：此时每个节点的值只出现一次，不需要二次遍历
        if(maxCount==1) return header.next;

        p = header;//重头开始
        while(p.next!=null){
            if(map.get(p.next.val)>1)   {
                p.next = p.next.next;
            }else p = p.next;
            if(p == null) break;
            
        }
        return header.next;
    }
}

golang 解法, 执行用时: 216 ms, 内存消耗: 20.3 MB, 提交时间: 2023-10-17 15:18:01

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicatesUnsorted(head *ListNode) *ListNode {
    var m = make(map[int]int)
    for h:=head;h!=nil;h = h.Next{
        m[h.Val]++
    }
    dummy := &ListNode{0,head}
    pre := dummy
    for h:=head;h!=nil;h = h.Next{
        if m[h.Val]>1{
            pre.Next = h.Next
        }else{
            pre = h
        }
    }
    return dummy.Next
}

python3 解法, 执行用时: 1016 ms, 内存消耗: 57 MB, 提交时间: 2023-10-17 15:16:37

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:
        b = ListNode(0, head)
        d = {}
        p = head
        # 第一次遍历，查出重复的节点，
        while p:
            if p.val not in d:
                d[p.val] = 1
                b = b.next
            else:
                d[p.val] +=1
                b.next = b = p.next
            p = p.next
        w = pr = ListNode(0, head)
        
        while head:
            if d[head.val] > 1:
                pr.next = head.next
            else:
                pr = pr.next
            head = head.next
        return w.next

python3 解法, 执行用时: 992 ms, 内存消耗: 57.2 MB, 提交时间: 2023-10-17 15:13:03

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:
        dup = set()
        pre = set()
        cur = head
        while cur:
            if cur.val in pre:
                dup.add(cur.val)
            pre.add(cur.val)
            cur = cur.next

        ans = ListNode(-1)  # 哨兵节点
        node = ans
        while head:
            if head.val not in dup:
                tmp = head.next
                head.next = None
                node.next = head
                node = node.next
                head = tmp
            else:
                head = head.next
        return ans.next