Remove Duplicates from Sorted List II

描述

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

For example,

Given 1->2->3->3->4->4->5, return 1->2->5.

Given 1->1->1->2->3, return 2->3.

分析

无

递归版

  1. // Remove Duplicates from Sorted List II
  2. // 递归版，时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4.     public ListNode deleteDuplicates(ListNode head) {
  5.         if (head ==null || head.next == null) return head;
  7.         ListNode p = head.next;
  8.         if (head.val == p.val) {
  9.             while (p != null && head.val == p.val) {
  10.                 p = p.next;
  11.             }
  12.             return deleteDuplicates(p);
  13.         } else {
  14.             head.next = deleteDuplicates(head.next);
  15.             return head;
  16.         }
  17.     }
  18. };

迭代版

  1. // Remove Duplicates from Sorted List II
  2. // 迭代版，时间复杂度O(n)，空间复杂度O(1)
  3. public class Solution {
  4.     public ListNode deleteDuplicates(ListNode head) {
  5.         if (head == null) return head;
  7.         ListNode dummy = new ListNode(Integer.MAX_VALUE); // 头结点
  8.         dummy.next = head;
  9.         ListNode prev = dummy, cur = head;
  10.         while (cur != null) {
  11.             boolean duplicated = false;
  12.             while (cur.next != null && cur.val == cur.next.val) {
  13.                 duplicated = true;
  14.                 cur = cur.next;
  15.             }
  16.             if (duplicated) { // 删除重复的最后一个元素
  17.                 cur = cur.next;
  18.                 continue;
  19.             }
  20.             prev.next = cur;
  21.             prev = prev.next;
  22.             cur = cur.next;
  23.         }
  24.         prev.next = cur;
  25.         return dummy.next;
  26.     }
  27. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/linked-list/remove-duplicates-from-sorted-list-ii.html