本文主要是介绍LeetCode题练习与总结：删除排序链表中的重复元素--83，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目描述
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2] 输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3] 输出：[1,2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
二、解题思路
1. 判断链表是否为空，如果为空，直接返回null。
2. 创建一个哑结点（dummy node），它的next指针指向链表的头节点。哑结点的目的是为了方便删除头节点。
3. 使用两个指针，current和next，分别指向哑结点和哑结点的下一个节点。
4. 遍历链表，比较current的下一个节点和下下个节点的值：
- 如果它们的值相同，则删除下下个节点。
- 如果它们的值不同，则将current指向下一个节点。
5. 继续遍历，直到current的下一个节点为空。
6. 返回哑结点的下一个节点，即新链表的头节点。
三、具体代码
class Solution {public ListNode deleteDuplicates(ListNode head) {if (head == null) {return null;}ListNode dummy = new ListNode(0);dummy.next = head;ListNode current = dummy;while (current.next != null && current.next.next != null) {if (current.next.val == current.next.next.val) {current.next = current.next.next;} else {current = current.next;}}return dummy.next;}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 我们遍历了整个链表一次，其中 n 是链表的长度。
- 在每次迭代中，我们进行了常数时间的操作，比如比较节点值和修改节点指向。
- 因此，总的时间复杂度是 O(n)。
2. 空间复杂度
- 我们只使用了固定数量的额外空间，即哑结点
dummy和几个指针变量current。 - 这些额外空间的使用不依赖于输入链表的大小，因此空间复杂度是 O(1)。
五、总结知识点
1. 链表（Linked List）：
- 链表是一种常见的基础数据结构，由一系列节点组成，每个节点包含数据和一个或多个指向其他节点的引用（链接）。
- 在这个问题中，我们操作的是单向链表，每个节点只包含数据和指向下一个节点的引用。
2. 哑结点（Dummy Node）：
- 哑结点是一个辅助节点，通常用于简化链表操作，尤其是在处理头节点时。
- 在这个问题中，哑结点被用来简化删除头节点的操作，因为头节点可能被重复删除。
3. 指针（Pointer）：
- 在链表的操作中，指针用于跟踪当前处理的节点。
- 在这个问题中，
current指针用于遍历链表，dummy指针用于简化头节点的删除操作。
4. 循环（Loop）：
- 循环用于遍历链表中的每个节点。
- 在这个问题中，
while循环用于遍历链表，直到到达链表的末尾。
5. 链表操作：
- 链表的基本操作包括遍历、修改节点数据和修改节点指向。
- 在这个问题中，我们修改了节点的
next指针，以删除重复的元素。
6. 条件语句（Conditional Statements）：
- 条件语句用于根据条件执行不同的代码路径。
- 在这个问题中，
if语句用于检查当前节点的下一个节点和下下个节点的值是否相等，以决定是否删除节点。
7. 算法设计：
- 这个问题涉及到简单的算法设计，即如何高效地删除链表中的重复元素。
- 通过利用链表的有序性，我们可以通过一次遍历来删除重复元素，这比先排序再删除重复元素更高效。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
这篇关于LeetCode题练习与总结：删除排序链表中的重复元素--83的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
