Remove Duplicates from Sorted List

描述

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,

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

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

分析

无

递归版

  1. // Remove Duplicates from Sorted List
  2. // 递归版，时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4.     public ListNode deleteDuplicates(ListNode head) {
  5.         if (head == null) return head;
  6.         ListNode dummy = new ListNode(head.val + 1); // 值只要跟head不同即可
  7.         dummy.next = head;
  9.         recur(dummy, head);
  10.         return dummy.next;
  11.     }
  12.     private static void recur(ListNode prev, ListNode cur) {
  13.         if (cur == null) return;
  15.         if (prev.val == cur.val) { // 删除head
  16.             prev.next = cur.next;
  17.             recur(prev, prev.next);
  18.         } else {
  19.             recur(prev.next, cur.next);
  20.         }
  21.     }
  22. };

迭代版

  1. // Remove Duplicates from Sorted List
  2. // 迭代版，时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public ListNode deleteDuplicates(ListNode head) {
  5.         if (head == null) return null;
  7.         for (ListNode prev = head, cur = head.next; cur != null; cur = prev.next) {
  8.             if (prev.val == cur.val) {
  9.                 prev.next = cur.next;
  10.             } else {
  11.                 prev = cur;
  12.             }
  13.         }
  14.         return head;
  15.     }
  16. };

相关题目

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