【题目描述】
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving onlydistinctnumbers from the original list.
给定一个排序链表,删除所有重复的元素只留下原链表中没有重复的元素。
【题目链接】
www.lintcode.com/en/problem/remove-duplicates-from-sorted-list-ii/
【题目解析】
上题为保留重复值节点的一个,这题删除全部重复节点,看似区别不大,但是考虑到链表头不确定(可能被删除,也可能保留),因此若用传统方式需要较多的if条件语句。这里介绍一个处理链表头节点不确定的方法——引入dummy node.
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *node= dummy;
引入新的指针变量dummy,并将其next变量赋值为head,考虑到原来的链表头节点可能被删除,故应该从dummy处开始处理,这里复用了head变量。考虑链表A->B->C,删除B时,需要处理和考虑的是A和C,将A的next指向C。如果从空间使用效率考虑,可以使用head代替以上的node,含义一样,node比较好理解点。
与上题不同的是,由于此题引入了新的节点dummy,不可再使用node->val == node->next->val,原因有二:
1此题需要将值相等的节点全部删掉,而删除链表的操作与节点前后两个节点都有关系,故需要涉及三个链表节点。且删除单向链表节点时不能删除当前节点,只能改变当前节点的next指向的节点。
2在判断val是否相等时需先确定node->next和node->next->next均不为空,否则不可对其进行取值。
【参考答案】
www.jiuzhang.com/solutions/remove-duplicates-from-sorted-list-ii/