题目

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

  1. Input: 1->2->3->3->4->4->5
  2. Output: 1->2->5

Example 2:

  1. Input: 1->1->1->2->3
  2. Output: 2->3

题意

将有序链表中所有值重复的结点删除，只保留值不重复的结点。

思路

遍历链表，找到所有值不重复的结点，将其单独取出来依次加入到新链表中。

代码实现

Java

  1. class Solution {
  2.     public ListNode deleteDuplicates(ListNode head) {
  3.         ListNode ans = null, last = null;
  5.         while (head != null) {
  6.             ListNode temp = head.next;
  7.             int count = 0;
  9.             // 判断head的值是否重复，并找到下一个值不同的结点
  10.             while (temp != null && temp.val == head.val) {
  11.                 temp = temp.next;
  12.                 count++;
  13.             }
  15.             if (count == 0) {
  16.                 head.next = null;        // 将该结点单独取出，断开与之后结点的联系
  17.                 if (ans == null) {
  18.                     ans = head;
  19.                     last = head;
  20.                 } else {
  21.                     last.next = head;
  22.                     last = last.next;
  23.                 }
  24.             }
  26.             head = temp;
  27.         }
  29.         return ans;
  30.     }
  31. }

JavaScript

  1. /**
  2.  * @param {ListNode} head
  3.  * @return {ListNode}
  4.  */
  5. var deleteDuplicates = function (head) {
  6.   const dummy = new ListNode()
  7.   let p = dummy
  8.   while (head) {
  9.     if (head.next && head.next.val === head.val) {
  10.       const val = head.val
  11.       while (head && head.val === val) {
  12.         head = head.next
  13.       }
  14.     } else {
  15.       p.next = head
  16.       p = head
  17.       head = head.next
  18.       p.next = null
  19.     }
  20.   }
  21.   return dummy.next
  22. }