82.删除排序链表中的重复元素II

链接：82.删除排序链表中的重复元素II
难度：Medium
标签：链表、双指针
简介：给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

题解 1 - java

• 编辑时间：2020-02-13
• 执行用时：5ms
• 内存消耗：44.3MB
• 编程语言：java
• 解法介绍：使用 map 储存元素，若元素不存在则 put 元素值为 1，若存在则值加 1，最后遍历若值不为 1 则删除。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
			return null;
		}
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		ListNode newHead = new ListNode(0);
		newHead.next = head;
		while (head != null) {
			int tem = head.val;
			if (map.containsKey(tem)) {
				int num = map.get(tem) + 1;
				map.put(tem, num);
			} else {
				map.put(tem, 1);
			}
			head = head.next;
		}
		head = newHead;
		while (head.next != null) {
			int val = head.next.val;
			if (map.get(val) > 1) {
				head.next = head.next.next;
			} else {
				head = head.next;
			}
		}
		return newHead.next;
    }
}

题解 2 - typescript

• 编辑时间：2021-03-06
• 执行用时：80ms
• 内存消耗：39.9MB
• 编程语言：typescript
• 解法介绍：利用已排序的特点直接进行比较。

function deleteDuplicates(head: ListNode | null): ListNode | null {
  if (head === null) return null;
  const dummyHead = new ListNode(0, head);
  let p = dummyHead;
  let q: ListNode | null = dummyHead;
  while (p.next !== null) {
    if (p.next.next && p.next.val === p.next.next.val) {
      q = p.next.next;
      while (q && q.val === p.next.val) q = q.next;
      p.next = q;
    } else {
      p = p.next;
    }
  }
  return dummyHead.next;
}

题解 3 - typescript

• 编辑时间：2021-03-25
• 执行用时：96ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：创建虚拟头节点依次比较值。

function deleteDuplicates(head: ListNode | null): ListNode | null {
  if (head === null) return null;
  const dummyHead = new ListNode(0, head);
  let p: ListNode | null = dummyHead;
  while (p !== null) {
    let q: ListNode | null = p.next;
    if (q === null || q.next === null) break;
    else if (q.val !== q.next.val) {
      p.next = q;
      p = q;
    } else {
      const val = q.val;
      while (q !== null && q.val === val) q = q.next;
      p.next = q;
    }
  }
  return dummyHead.next;
}

题解 4 - python

• 编辑时间：2024-01-15
• 执行用时：44ms
• 内存消耗：16.9MB
• 编程语言：python
• 解法介绍：遍历。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p = tmp_head = ListNode(0, head)
        while p.next:
            next = p.next
            val = next.val
            while next and next.val == val: next = next.next
            if p.next.next == next: p = p.next
            else: p.next = next
        return tmp_head.next

题解 5 - rust

• 编辑时间：2024-01-15
• 内存消耗：2.11MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut tmp_head = Box::new(ListNode::new(0));
        tmp_head.next = head;
        let mut p = &tmp_head;
        let mut map = [0; 300];
        while let Some(ref next) = p.next {
            map[(next.val + 100) as usize] += 1;
            p = next;
        }
        let mut p = &mut tmp_head;
        while let Some(next) = p.next.take() {
            if map[(next.val + 100) as usize] > 1 {
                p.next = next.next;
            } else {
                p.next = Some(next);
                p = p.next.as_mut().unwrap();
            }
        }
        tmp_head.next.take()
    }
}