82. 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.

---

这道题将链表中有重复的数据全部去除，第一种方式：使用两个vector（nodes1和nodes2），遍历一遍链表。如果当前节点的数字不存在第一个nodes1中则将其添加进去，如果已经存在了则将其加入到nodes2中。这样的话遍历完成之后，nodes1中存放的数据是不重复的，nodes2中存放的则是nodes1已经存在数据。比如最开始的1->2->3->3->4->4->5，那么遍历完成之后，nodes1中存放的有：1、2、3、4、5，而nodes2存放的有：3、4。然后对集合进行求差集运算，求出只存在于nodes1中的而不存在于nodes2的，就是1、2、5.

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) {
            return nullptr;
        }

        vector<int> nodes1;
        vector<int> nodes2;
        vector<int> resultnodes;
        ListNode* result = new ListNode(0);
        ListNode* temp = result;

        while(head) {

            if(find(nodes1.begin(),nodes1.end(),head->val) == nodes1.end()) {//如果不存在则加入到nodes1中
                nodes1.push_back(head->val);
                //cout << "nodes1:" << head->val << endl;
            } else {//如果存在则加入nodes2中
                nodes2.push_back(head->val);
                //cout << "nodes2:" << head->val << endl;
            }
            head = head->next;
        }

        //取差集，从小到大的排序才可以
        set_difference(nodes1.begin(),nodes1.end(),nodes2.begin(),nodes2.end(),inserter(resultnodes,resultnodes.begin()));//取两个set的差集

        for(vector<int>::iterator it=resultnodes.begin();it!=resultnodes.end();it++) {
            //cout << *it << endl;
            ListNode* node = new ListNode(*it);
            temp->next = node;
            temp = node;
        }

        //return nullptr;
        return result->next;

    }
};

---

第二种是使用两个指针和一个flag，最初preCur指向一个节点，Cur指向后一个节点。然后开始遍历，当preCur和Cur相等的时候flag赋值为1，cur继续向后移动，当preCur和Cur不相等的时候，flag赋值为0，并且让preCur等于Cur，Cur继续向后移动，这样就可以将前面相等的数据全部跳过去。然后如果此时移动过Cur之后还不相等并且flag=0，那么就可以将preCur加入到最终要返回的链表中了。需要注意一下Cur是不是最后一个，如果是的话直接将其加入即可。

#include <iostream>
#include <unordered_set>
#include <set>
#include <algorithm>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {

        if(!head || !head->next) {
            return head;
        }

        ListNode* preCur = head;
        ListNode* cur = head->next;
        ListNode* result = new ListNode(0);
        ListNode* temp = result;
        int flag = 0;
        while(cur) {
            if(preCur->val == cur->val) {//如果相等的话,标记位赋值为1
                flag = 1;
            } else {//不相等，标记为赋值为0，并且如果此时标记为已经为0了，那么加入最终的链表中
                if(flag == 0) {
                    ListNode* node = new ListNode(preCur->val);
                    temp->next = node;
                    temp = node;
                }
                preCur = cur;
                flag = 0;
                if(!cur->next) {//如果下一个没有内容了，将此时的cur也加入
                    temp->next = cur;
                }
            }
            cur = cur->next;
        }

        return result->next;

        /*if(!head) {
            return nullptr;
        }

        vector<int> nodes1;
        vector<int> nodes2;
        vector<int> resultnodes;
        ListNode* result = new ListNode(0);
        ListNode* temp = result;

        while(head) {

            if(find(nodes1.begin(),nodes1.end(),head->val) == nodes1.end()) {//如果不存在则加入到nodes1中
                nodes1.push_back(head->val);
                //cout << "nodes1:" << head->val << endl;
            } else {//如果存在则加入nodes2中
                nodes2.push_back(head->val);
                //cout << "nodes2:" << head->val << endl;
            }
            head = head->next;
        }

        //取差集，从小到大的排序才可以
        set_difference(nodes1.begin(),nodes1.end(),nodes2.begin(),nodes2.end(),inserter(resultnodes,resultnodes.begin()));//取两个set的差集

        for(vector<int>::iterator it=resultnodes.begin();it!=resultnodes.end();it++) {
            //cout << *it << endl;
            ListNode* node = new ListNode(*it);
            temp->next = node;
            temp = node;
        }

        return result->next;*/

    }
};

int main() {
    Solution s;

    ListNode node1(1);
    ListNode node2(1);
    ListNode node3(2);
    ListNode node4(2);
    ListNode node5(3);
    ListNode node6(4);

    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;
    node4.next = &node5;
    node5.next = &node6;

    ListNode* p = s.deleteDuplicates(&node1);

    while(p) {
        cout << p->val;
        cout << endl;
        p = p->next;
    }

}