面试题02.01.移除重复节点

链接：面试题02.01.移除重复节点
难度：Easy
标签：哈希表、链表、双指针
简介：编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

题解 1 - typescript

• 编辑时间：2020-06-27
• 执行用时：92ms
• 内存消耗：40.6MB
• 编程语言：typescript
• 解法介绍：利用 Set 储存已遍历过的节点值进行是否重复的判断。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function removeDuplicateNodes(head: ListNode | null): ListNode | null {
  if (head === null) return null;
  const set = new Set([head.val]);
  let temp = head;
  while (temp.next !== null) {
    const val = temp.next.val;
    if (set.has(val)) {
      temp.next = temp.next.next;
    } else {
      set.add(val);
      temp = temp.next as ListNode;
    }
  }
  return head;
}

题解 2 - typescript

• 编辑时间：2020-06-27
• 执行用时：584ms
• 内存消耗：40.1MB
• 编程语言：typescript
• 解法介绍：用双重循环判断是否重复，利用时间换空间。

function removeDuplicateNodes(head: ListNode | null): ListNode | null {
  if (head === null) return null;
  let temp1: ListNode | null = head;
  while (temp1 !== null) {
    const val = temp1.val;
    let temp2: ListNode | null = temp1;
    while (temp2 !== null && temp2.next !== null) {
      if (temp2.next.val === val) temp2.next = temp2.next.next;
      else temp2 = temp2.next;
    }
    temp1 = temp1.next;
  }
  return head;
}