当前位置：首页 > news >正文

数据结构与算法之链表: Leetcode 83. 删除排序链表中的重复元素 (Typescript版)

news 2025/8/14 4:25:13

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

https://leetcode.cn/problems/remove-duplicates-from-sorted-list/

描述

给定一个已排序的链表的头 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 ）方案 1

/*** 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 {let p = head;while(p?.next) {// 检测相邻两位是否相等const isEqual = p.val === p.next.val // 相等则移动两位，否则正常移动一位isEqual ? (p.next = p.next.next) : (p = p.next)}// 原路返回headreturn head;
};

解题思路
- 链表是有序的，重复链表一定相邻
- 遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值
- 删除的方式就是当前元素直接链接下下个元素
解题步骤
- 遍历链表，如果发现当前元素和下个元素值相同就删除下个元素值
- 遍历结束后，返回原链表头即可

2 ）方案 2

/*** 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 {let cur = headlet next = curwhile(cur) {do {next = next.next} while(next && cur.val === next.val)cur.next = nextcur = cur.next}return head
};