82. Remove Duplicates from Sorted List II 移除有序链表中的重复项之二

[GH1995]

82. Remove Duplicates from Sorted List II

Difficulty: Medium

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

Example 1:

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

Example 2:

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

Solution

Language: C++

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
      if (!head || !head->next) return head;
​
      auto dummy = new ListNode(INT_MIN);
      dummy->next = head;
      auto slow = dummy;
​
      while (slow->next) {
        auto fast = slow->next; // fast 用于探测，被假定为重复元素
        // 处理有重复的情况
        while (fast->next && fast->next->val == fast->val) // fast 遇到相同的则继续往下
          fast = fast->next;
        // fast 跑完的时候应该在重复的最后一个元素
        // 或者压根没跑
​
        if (fast != slow->next)  // 有重复
          slow->next = fast->next; // 这里删除了 fast 中所有相同的元素
        else // 没重复
          slow = slow->next; // fast 遍历的第一个元素就不相同
      }
​
      return dummy->next;
    }
};

[GH1995]

1. 开始的时候 fast = slow->next
2. fast负责跑完所有的重复元素，当fast停留在最后一个重复元素上时slow->next = fast->next

---

detect                        +                            +
                              |                            |
     +-------+     +-------+  |   +-------+     +-------+  |  +-------+
     |       |     |       |  |   |   3   |     |   3   |  |  |       |
     +-------+     +-------+  |   +---^---+     +-------+  |  +-------+
                              |       +                    |
       dummy         slow     |      fast                  |
                              |                            |
                              |                            |
run over                      |                            |
                              |                            |
     +-------+     +-------+  |   +-------+     +-------+  |   +-------+
     |       |     |       |  |   |   3   |     |   3   |  |   |       |
     +-------+     +-------+  |   +-------+     +---^---+  |   +-------+
                              |                     +      |
       dummy         slow     +                    fast    +

                              +---------------------------->
                                       delete

                                                slow->next = fast->next

这里代码也是要看的

设置了

• slow 监察上一个不同的元素
• fast 跑所有相同的元素

1. fast处理有重复的情况
2. 处理fast跑完了的情况
   • 有重复slow->next= fast->next
   • 没重复slow自己跑一步