题目描述

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

解题思路

  • 因为链表是有序的 , 所以重复元素一定相邻
  • 遍历链表, 若发现当前元素和下个元素值相同, 就删除下个元素
  • 遍历结束后, 返回原链表头部

代码实现

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} head
  10.  * @return {ListNode}
  11.  */
  12. var deleteDuplicates = function(head) {
  13.     let p = head
  14.     while(p){
  15.         /** p.next?.val 这里是为了避免当p.next为null的时候报错 */
  16.         if(p.val === p.next?.val){
  17.             p.next = p.next.next
  18.             /** 删除重复节点后p指针并不后移,避免下一节点也是重复节点的情况 */
  19.         }else{
  20.             p = p.next
  21.         }
  22.     }
  23.     return head     
  24. };

时间复杂度 O(n)
空间复杂度 O(1)