0083._Remove_Duplicates_From_Sorted_List

083. Remove Duplicates From Sorted List

难度: Easy

刷题内容

原题连接

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

内容描述

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

示例 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
};