Skip to content

083. Remove Duplicates From Sorted List

难度: Easy

刷题内容

原题连接

内容描述

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

解题方案

思路 1 - 时间复杂度: O(N)

- 空间复杂度: O(2N)

暴力解法:将链表转化为数组,对数组去重,然后数组转换为链表

执行用时 :100 ms, 在所有 JavaScript 提交中击败了75.87%的用户

内存消耗 :36.7 MB, 在所有 JavaScript 提交中击败了7.05%的用户

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
  if (!head) {
    return null
  }
  let array = listNodeToArray(head)
  return arrayToListNode([...new Set(array)])
};


function listNodeToArray (head) {
  let array = []
  while (head) {
    array.push(head.val)
    head = head.next
  }
  return array
}

function  arrayToListNode(array) {
  if(!array || !array.length) {
    return null
  }

  let node
  let head = new ListNode(array[0])
  let pnode = head  //pnode变量用来保存前一个节点

  for(let i = 1; i < array.length; i++) {
    node = new ListNode(array[i])
    pnode.next = node   //将前一个节点的next指向当前节点
    pnode = node   //将node赋值给pnode
  }

  return head
}

思路 2 - 时间复杂度: O(N)

- 空间复杂度: O(1)

快慢指针:每次循环,判断当前的值与下一个是否相等,如果相等,快指针(head)向前移动,慢指针(slow)原地不动;如果不等则把下一个节点连接到慢指针后,再将快慢指针都向前移动。

执行用时 :92 ms, 在所有 JavaScript 提交中击败了91.01%的用户

内存消耗 :35.7 MB, 在所有 JavaScript 提交中击败了69.46%的用户

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
  if (!head) {
    return null
  }
  let slow = head
  let result = slow
  while (head) {
    if (head.next && (head.val === head.next.val)) {
      head = head.next
    } else {
      slow.next = head.next
      slow = slow.next
      head = head.next
    }
  }
  return result
};


回到顶部