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

Tips

题目类型: 链表, 快慢指针

相关题目:

• 26. 删除排序数组中的重复项
• 27. 移除元素
• 61. 旋转链表
• 141. 环形链表
• 142. 环形链表 II
• 234. 回文链表

题目

存在一个按升序排列的链表, 给你这个链表的头节点 head, 请你删除所有重复的元素, 使每个元素只出现一次. 返回同样按升序排列的结果链表.

提示:

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序排列

示例

输入: head = [1, 1, 2, 3, 3]

输出: [1, 2, 3]

题解

JavaScript - 直观解法

因为链表是升序的, 因此如果有重复的值, 这些重复的值也一定也是在一起的. 因此一趟循环, 只要当前节点值等于下个节点的值, 直接删除下个节点即可.

/**
 * 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 head
  
  let curr = head

  while (curr && curr.next) {
    if (curr.next.val === curr.val) {
      curr.next = curr.next.next
    } else {
      curr = curr.next
    }
  }

  return head
}

JavaScript - 双指针

因为链表有天然的方法 curr.next = curr.next.next 来删除下个元素, 所以用左边的直观解法就可以, 不过更通用的解法是使用快慢指针.

这个解法可以跟 26. 删除排序数组中的重复项 对比着看, 一个模子, 只不过一个是数组, 一个是链表.

var deleteDuplicates = function (head) {
  if (!head) return head

  let slow = head,
    fast = head

  while (fast) {
    if (fast.val !== slow.val) {
      slow.next = fast
      slow = slow.next
    }

    fast = fast.next
  }

  // 断开与后面重复元素的连接
  slow.next = null

  return head
}