题目

题目来源：力扣（LeetCode）

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


示例 1：
image.png

输入：head = [1,1,2]
输出：[1,2]

示例 2：
image.png

输入：head = [1,1,2,3,3]
输出：[1,2,3]

思路分析

双指针法

由题意可知，给定的链表是已经排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。

1、我们分别定义一个慢指针slow，一个快指针fast，初始时慢指针指向头节点，快指针指向头节点的下一个节点：

2、然后开始遍历链表，如果慢指针slow所指向的节点值与快指针fast所指向的节点值相同，说明出现了重复的元素，此时我们要做的事情就是将慢指针的后继指针指向快指针所指向节点的下一个节点，快指针指向其所指节点的下一个节点：
3、继续遍历链表，如果慢指针所指向节点的值与快指针所指向节点的值不相等，则分别将慢指针slow和快指针分别往后移动一位：
4、当 fast 指针指向null时，说明链表已经遍历完了，此时链表中已经没有重复的元素了，返回链表的头节点即可：

  1. var deleteDuplicates = function(head) {
  2.     if (head == null) return null;
  3.     // 定义慢指针slow 指向头节点
  4.     let slow = head;
  5.     // 定义快指针指向头节点的下一个节点
  6.     let fast = slow.next;
  7.     // 遍历链表，当快指针fast指向null时，说明链表已经遍历完毕，链表也已去重完毕
  8.     while (fast != null) {
  9.         if (slow.val === fast.val) {
  10.             // 当慢指针所指向节点的值与快指针所指向节点的值相等
  11.             // 将慢指针的后继指针指向快指针所指节点的下一个节点
  12.             slow.next = fast.next;
  13.             // 快指针指向其所指节点的下一个节点
  14.             fast = fast.next;
  16.         } else {
  17.             // 慢指针所指节点的值与快指针所指节点的值不相等
  18.             // 慢指针和快指针分别往后移动一位
  19.             slow = fast;
  20.             fast = slow.next
  21.         }
  22.     } 
  24.     // 链表去重完毕后，将慢指针所指节点 (链表尾节点) 的后继指针指向 null
  25.     slow.next = null
  26.     // 返回链表的头节点
  27.     return head
  28. };

单指针法

由于给定的链表是已经排好序的，因此重复的元素在链表中出现的位置是连续的，所以我们只需要对链表进行一次遍历，就可以删除重复的元素。

我们定义一个 curr 指针，将其指向链表的头节点，然后开始遍历链表，如果curr所指节点的值与 curr.next 对应节点的值相等，那么我们就将 curr.next 从链表中删除，具体的做法是将 curr的后继指针指向 curr.next.next 。

如果curr所指节点的值与 curr.next 对应节点的值不相等，说明链表中已不存在其它与 curr 所指节点相同的节点，此时我们可以将curr指向 curr.next。

当遍历完整个链表后，返回链表的头节点即可。

  1. var deleteDuplicates = function(head) {
  2.     if (!head) return head;
  4.     // 定义一个 curr 指针，指向头节点
  5.     let curr = head;
  6.     // 遍历链表
  7.     while (curr.next) {
  8.         // 如果 curr 指针所指节点与其所指节点的下一个节点的值相等，说明这两个节点是重复的
  9.         // 将 curr 所指节点的下一个节点删除
  10.         if (curr.val === curr.next.val) {
  11.             // 将curr所指节点的后继指针指向当前节点的下一个节点的下一个节点
  12.             curr.next = curr.next.next;
  13.         } else {
  14.             // curr 指针所指节点与其所指节点的下一个节点的值不相等
  15.             // curr 指针往后移动一位
  16.             curr = curr.next;
  17.         }
  18.     }
  19.     // 链表遍历完毕，链表也已去重完毕，返回链表的头节点
  20.     return head;
  21. };