83、删除排序链表中的重复元素

;(function () {
  /**
     * 83. 删除排序链表中的重复元素
     * 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
     * 
     * 输入：head = [1,1,2]
     * 输出：[1,2]
     * 
     * 输入：head = [1,1,2,3,3]
     * 输出：[1,2,3]
     * 
     * 提示：链表中节点数目在范围 [0, 300] 内
        -100 <= Node.val <= 100
        题目数据保证链表已经按升序 排列
     */

  /**
   * 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 deleteDuplicates(head: ListNode | null): ListNode | null {
    // 方法一：哈希Set
    // if (!head) {
    //     return head;
    // }
    // const set = new Set();
    // const prevHead = new ListNode(0);
    // let prev = prevHead;
    // while(head) {
    //     if (set.has(head.val)) {
    //         prev.next = null
    //     } else {
    //         set.add(head.val)
    //         prev.next = head
    //         prev = prev.next
    //     }
    //     head = head.next
    // }
    // return prevHead.next

    // 方法二： 遍历法（官方）
    if (!head) {
      return head
    }
    let cur = head
    while (cur.next) {
      if (cur.val === cur.next.val) {
        cur.next = cur.next?.next
      } else {
        cur = cur.next
      }
    }
    return head
  }
})()