题解 | #删除有序链表中重复的元素-II#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        int flag = 0;   // 重复标记，没有重复为0，有重复为1
        stack<ListNode*> st;    // 栈内存放不重复的元素
        ListNode* phead = new ListNode(-1); // 创建遍历链表的头节点
        phead->next = head; // 头节点指向head
        st.push(phead); // 将头节点压入栈中
        while(phead->next){
            if(st.top()->val == phead->next->val){  // 如果phead->next 与栈顶元素相等
                phead = phead->next;    // phead后移
                flag = 1;   // 将重复标记置为1
            } else {    // 如果phead->next与栈顶元素不同
                if(flag == 0){  // 检查重复标记的值，若为0，表示没有重复节点
                    st.push(phead->next);   // 将phead->next压栈
                    phead = phead->next;    // phead指针后移
                } 
                else if(flag == 1){ // 如果重复标记为1，表示有重复元素
                    st.pop();   // 重复元素为栈顶元素，先将栈顶元素弹出
                    st.push(phead->next);   // 将phead->nexg压栈
                    phead = phead->next;    // phead指针后移
                    flag = 0;   // 重置重复标记flag
                }
            }
        }
        if(flag == 1) st.pop(); // 如果循环结束flag仍为1，说明栈顶元素是重复元素，需弹出
        ListNode* tail = NULL;  // 创建尾结点
        ListNode* result = st.top();    // 创建返回链表头结点（栈顶元素）
        st.pop();   // 弹栈
        result->next = tail;    // 将头尾结点相连
        while(!st.empty()){ // 当栈不为空时
            ListNode* temp = result;    // 临时节点保存result节点
            result = st.top();  // result节点指向栈顶结点
            result->next = temp;    // result->next指向临时节点，建立连接关系
            st.pop();   // 弹出栈顶结点，直到栈为空
        }
        return result->next;
    }
};