题目描述
编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入:[1, 2, 3, 3, 2, 1]
输出:[1, 2, 3]
示例2:
输入:[1, 1, 1, 1, 2]
输出:[1, 2]
提示:
链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
进阶:
如果不得使用临时缓冲区,该怎么解决?
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/remove-duplicate-node-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
开始解题(php)
if ($head == null) {
return $head;
}
$cur = $head;
while ($cur != null) {
$prev = $cur;
$nextNode = $cur->next;
while ($nextNode != null) {
if ($nextNode->val == $cur->val) {
$prev->next = $nextNode->next;
} else {
$prev = $nextNode;
}
$nextNode = $nextNode->next;
}
$cur = $cur->next;
}
return $head;
关于链表(赋值指向的是同一个链表对象)
逐步验算
示例1(输入:[1, 2, 3, 1] 输出:[1, 2,3])
第1次外循环,第1次内循环
第1次外循环,第2次内循环
第1次外循环,第3次内循环(把第1个节点重复的第4个节点从原来的链表删除)
第2次外循环
第3次外循环
示例2( 输入:[1, 2, 3, 3, 2, 1] ,输出:[1, 2, 3])
第1次外循环
第6个节点的值和第1个节点的相同,则把第5个节点和第7个空节点链接(等同于把第6个节点删除了)
第2次外循环
第3次外循环
实际应用
这个函数的实际应用是用于删除链表中重复的节点,使得链表中每个节点的值都不相同。该函数可以用于解决一些问题,例如:
- 删除排序链表中的重复元素:如果一个链表是有序的,并且有重复元素,可以使用该函数来删除重复元素,保留每个元素的一个实例。
- 删除未排序链表中的重复元素:即使链表是无序的,也可以使用该函数来删除链表中的重复元素,只需遍历链表并记录出现过的元素,当遇到重复元素时删除即可。
- 检测链表中是否存在重复元素:使用该函数可以遍历链表并检测是否存在重复元素,如果链表中存在重复元素,则返回删除重复元素后的链表头节点。
这个函数可以帮助解决一些链表相关的问题,提高代码的简洁性和效率。