题目描述（中等难度）

82. Remove Duplicates from Sorted List II - 图1

给一个链表，如果一个数属于重复数字，就把这个数删除，一个都不留。

解法一 迭代

只需要两个指针，一个指针 pre 代表重复数字的前边的一个指针，另一个指针 cur 用来遍历链表。d 代表哨兵节点，用来简化边界条件，初始化为 head 指针的前一个节点。p 代表 pre，c 代表 cur。

  1. d 1 2 3 3 3 4 cur 和 cur.next 不相等，pre 移到 cur 的地方，cur后移
  2. ^ ^ 
  3. p c 
  5. d 1 2 3 3 3 4 cur 和 cur.next 不相等，pre 移到 cur 的地方，cur后移
  6.   ^ ^
  7.   p c
  9. d 1 2 3 3 3 4 5 cur 和 cur.next 相等, pre 保持不变，cur 后移
  10.     ^ ^
  11.     p c
  13. d 1 2 3 3 3 4 5 cur 和 cur.next 相等, pre 保持不变，cur 后移
  14.     ^   ^
  15.     p   c
  17. d 1 2 3 3 3 4 5 cur 和 cur.next 不相等, pre.next 直接指向 cur.next， 删除所有 3，cur 后移
  18.     ^     ^
  19.     p     c
  21. d 1 2 4 5 cur 和 cur.next 不相等，pre 移到 cur 的地方，cur后移
  22.     ^ ^
  23.     p c
  25. d 1 2 4 5 遍历结束
  26.       ^ ^
  27.       p c
  1. public ListNode deleteDuplicates(ListNode head) { 
  2.     ListNode pre = new ListNode(0);
  3.     ListNode dummy = pre;
  4.     pre.next = head;
  5.     ListNode cur = head;
  6.     while(cur!=null && cur.next!=null){
  7.         boolean equal = false;
  8.         //cur 和 cur.next 相等，cur 不停后移
  9.         while(cur.next!=null && cur.val == cur.next.val){ 
  10.             cur = cur.next;
  11.             equal = true; 
  12.         }
  13.         //发生了相等的情况
  14.         // pre.next 直接指向 cur.next 删除所有重复数字
  15.         if(equal){
  16.             pre.next = cur.next; 
  17.             equal = false;
  18.         //没有发生相等的情况
  19.         //pre 移到 cur 的地方
  20.         }else{
  21.             pre = cur;
  22.         }
  23.         //cur 后移
  24.         cur = cur.next;
  25.     }
  26.     return dummy.next;
  27. }

时间复杂度：O（n）。

空间复杂度：O（1）。

解法二 递归

这里看到了一种递归的解法，分享一下。 主要分了两种情况，头结点和后边的节点相等，头结点和后边的节点不相等。

  1. public ListNode deleteDuplicates(ListNode head) {
  2.     if (head == null) return null;
  3.     //如果头结点和后边的节点相等
  4.     if (head.next != null && head.val == head.next.val) {
  5.         //跳过所有重复数字
  6.         while (head.next != null && head.val == head.next.val) {
  7.             head = head.next;
  8.         }
  9.         //将所有重复数字去掉后，进入递归
  10.         return deleteDuplicates(head.next);
  11.     //头结点和后边的节点不相等
  12.     } else {
  13.         //保留头结点，后边的所有节点进入递归
  14.         head.next = deleteDuplicates(head.next);
  15.     }
  16.     //返回头结点
  17.     return head;
  18. }

总

主要还是对链表的理解，然后就是指来指去就好了。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情