1. 题目描述

problem link

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

2. 解题

首先,为了应对头节点就是重复节点的特殊情况,还是在链表头部加一个dummyHead。

然后,用一个指针cur指向最后一个已经处理过的节点,初始情况下就是指向dummyHead。再拿一个指针tmp指向当前要处理的节点,并用一个变量val记录下这个节点的值,如下图所示:

然后,就是找后面有没有重复的元素,即让tmp->next的值和val比较,如果相等则让tmp向后走一步然后重复上述判断。对于上图的例子,这一流程走完如下图所示:

然后为了跳过中间重复的1直接让cur->next等于tmp->next就行了。

但假如中间的元素不是重复的,可知这种情况下tmp应该等于cur->next,对于这种情况直接让cur向后走就行了。所以最终这里用一个条件判断区分一下是否重复就行了。

3. 代码

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead == NULL) {
            return NULL;
        }
        ListNode* dummyHead =
            (ListNode *)malloc(sizeof(ListNode));
        dummyHead->next = pHead;

        ListNode* cur = dummyHead;
        ListNode* tmp;
        int val;

        while(cur->next) {
            val = cur->next->val;
            tmp = cur->next;
            while(tmp->next && tmp->next->val == val) {
                tmp = tmp->next;
            }
            if(tmp == cur->next) {
                cur = cur->next;
            }
            else {
                cur->next = tmp->next;
            }
        }

        return dummyHead->next;
    }
};
Last modification:September 8th, 2019 at 08:16 pm