面试题 02.01. 移除重复节点

面试题 02.01. 移除重复节点

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例 1:

输入：[1, 2, 3, 3, 2, 1]
 输出：[1, 2, 3]

示例 2:

输入：[1, 1, 1, 1, 2]
 输出：[1, 2]

提示：

1. 链表长度在[0, 20000]范围内。
2. 链表元素在[0, 20000]范围内。

进阶：
如果不得使用临时缓冲区，该怎么解决？

思路

set

遍历一次 set 存储，然后再根据 set 值生成新链表返回

双重循环

时间换空间，遍历一次，选择一个节点，然后再从该节点开始遍历一次，将链表里所有一样值的节点删除

解答

set

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var removeDuplicateNodes = function (head) {
  const setNum = new Set();
  while (head) {
    if (!setNum.has(head.val)) setNum.add(head.val);
    head = head.next;
  }
  const res = new ListNode();
  const arr = [...setNum.values()];
  let temp = res;
  while (arr.length) {
    temp.next = new ListNode(arr.shift());
    temp = temp.next;
  }
  return res.next;
};

双重循环

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var removeDuplicateNodes = function (head) {
  let p = head;
  while (p) {
    let q = p;
    while (q.next) {
      if (q.next.val === p.val) q.next = q.next.next;
      else q = q.next;
    }
    p = p.next;
  }
  return head;
};