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

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

• 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
};

• 上述是官方示例程序
• 这里while里面嵌套do while，这种写法让人眼前一亮