删除链表中的重复结点

╰+哭是因爲堅強的太久メ 2023-02-20 13:35 1阅读 0赞

题目描述  
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

我的修修补补一小时的辣鸡代码：

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
            val(x), next(NULL) {
        }
    };
    */
    class Solution {
        
    public:
        ListNode* deleteDuplication(ListNode* pHead)
        {
        
            if(pHead == NULL) return NULL;
            ListNode *pre , *temp = pHead;
            bool first = true;
            while(temp) {
        
                bool duplication = false;
                while(temp->next && temp->val == temp->next->val) {
        
                    duplication = true;
                    temp = temp->next;
                    }
                if(duplication) temp = temp->next;
                if(temp){
        
                    if(!temp->next || temp->next->val != temp->val) {
        
                        if(first) {
        
                            pHead = temp;
                            pre = pHead;
                            temp = temp->next;
                            first = false;
                        }else {
        
                            pre->next = temp;
                            pre = temp;
                            temp = temp->next;
                        }
                    }
                    else continue;
                } else {
        
                    if(first) {
        
                            pHead = temp;
                            first = false;
                        }else {
        
                            pre->next = temp;
                        }
                }
            }
            return pHead;
        }
    };

增加一个头节点可以减少判断：

class Solution {
        
    public:
        ListNode* deleteDuplication(ListNode* pHead)
        {
        
            ListNode *vhead = new ListNode(-1);
            vhead->next = pHead;
            ListNode *pre = vhead, *cur = pHead;        
            while (cur) {
        
                if (cur->next && cur->val == cur->next->val) {
        
                    cur = cur->next;
                    while (cur->next && cur->val == cur->next->val) {
        
                        cur = cur->next;
                    }
                    cur = cur->next;
                    pre->next = cur;
                }
                else {
        
                    pre = cur;
                    cur = cur->next;
                }
            }
            return vhead->next;
        }
    };