2022-04-18.md

每日一题 - 删除排序链表中的重复元素

信息卡片

• 时间：2022-04-18
• 题目链接：https://leetcode.com/problems/remove-duplicates-from-sorted-list/
• tag：链表

题目描述

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次。返回 已排序的链表。

示例1：

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

示例2：

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

提示：

• 链表中结点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

进阶：

思路分析

1. 升序排列，则链表中出现的元素是连续的
2. 遍历，如果下个结点和当前结点重复，则可以直接舍弃

参考答案

1. 循环 $O(n)$

空间复杂度：$O(1)$

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
function deleteDuplicates(head) {
  if (head === null) return head
  let currentNode = head
  while(null !== currentNode.next) {
    if (currentNode.val === currentNode.next.val) {
      currentNode.next = currentNode.next.next
    } else {
      currentNode = currentNode.next
    }
  }
  return head
}

2. 递归 $O(n)$

1. 每当处理完一个结点，链表变短。继续处理时和原链表的处理方式是一样的

function deleteDuplicates(head) {
  if (head === null || head.next === null) return head
  head.next = deleteDuplicates(head.next)
  return head.val === head.next.val ? head.next : head
}

递归处理，本质就是将链表压栈后倒序处理