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

迭代

依次遍历，每次都把相同的元素删掉

function deleteDuplicates(head: ListNode | null): ListNode | null {
  if (!head) {
    return null
  }

  let current = head // 当前区间的第一个元素

  // 依次遍历，每次都把相同的元素删掉
  // 如果 current.next 不存在，那么说明处理完了，不需要处理了
  while (current.next) {
    // 如果相同的话，直接删掉
    if (current.val === current.next.val) {
      current.next = current.next.next
    } else {
      // 如果不相同
      // 接着往下遍历
      current = current.next
    }
  }

  return head
}

双指针 1

记录当前相等的区间，当不等的时候删除中间元素

function deleteDuplicates(head: ListNode | null): ListNode | null {
  if (!head) {
    return null
  }

  let slow = head // 当前区间的第一个元素
  let fast = head.next // 当前区间的最后一个元素

  while (fast) {
    // 遇到不相等的
    // 需要将中间的删掉
    while (fast && slow.val === fast.val) {
      fast = fast.next
    }

    // 删掉中间同样的元素
    slow.next = fast

    // 开始处理新的区间
    slow = fast

    // 更新 fast
    if (fast) {
      fast = fast.next
    }
  }

  return head
}

双指针 2

和上面思路一样，不过处理的是不相等的情况

function deleteDuplicates(head: ListNode | null): ListNode | null {
  if (!head) {
    return null
  }

  let slow = head // 当前区间的第一个元素
  let fast = head.next // 当前区间的最后一个元素

  while (fast) {
    // 遇到不相等的
    // 需要将中间的删掉
    if (slow.val !== fast.val) {
      // 删掉中间同样的元素
      slow.next = fast

      // 开始处理新的区间
      slow = fast
    }

    // 更新 fast
    fast = fast.next
  }

  // 处理结束后 slow 和 fast 中间可能还有相同元素
  // 单独处理一下
  slow.next = null

  return head
}