如何删除链表中的重复节点
时间: 2024-01-06 21:06:13 浏览: 32
删除链表中的重复节点可以采用双重循环的方法,对于每一个节点,都遍历一遍链表,将其后面所有值与它相同的节点删除。具体实现可以参考以下代码:
```
struct ListNode* deleteDuplicates(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode *p = head;
while (p != NULL) {
struct ListNode *q = p;
while (q->next != NULL) {
if (q->next->val == p->val) {
q->next = q->next->next;
} else {
q = q->next;
}
}
p = p->next;
}
return head;
}
```
该代码的时间复杂度为 O(n^2),空间复杂度为 O(1)。如果要进一步优化时间复杂度,可以使用哈希表来记录已经出现过的节点值,这样就可以将时间复杂度优化到 O(n)。
相关问题
删除链表数据域相同节点
要删除链表中数据域相同的节点,可以使用两个指针进行遍历和删除操作。假设链表的节点定义如下:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
```
以下是删除链表中数据域相同节点的代码示例:
```python
def remove_duplicates(head):
if head is None:
return head
curr = head
while curr is not None:
runner = curr
while runner.next is not None:
if runner.next.val == curr.val:
runner.next = runner.next.next
else:
runner = runner.next
curr = curr.next
return head
```
这段代码首先检查链表是否为空,如果为空则直接返回。然后使用两个指针`curr`和`runner`进行节点遍历,其中`curr`指针用于遍历整个链表,而`runner`指针用于检查当前节点后面的节点是否与当前节点的数据域相同。如果相同,则将`runner`指针所指向的节点从链表中删除,否则继续遍历下一个节点。最后返回删除重复节点后的链表头部。
请注意,这里假设链表已经按照数据域的顺序进行排序。如果链表未排序,需要先对链表进行排序,然后再执行上述删除操作。
删除双向链表中的重复结点
要删除双向链表中的重复节点,可以使用哈希表记录已经出现的节点值,然后遍历链表,如果当前节点的值已经在哈希表中出现过了,就将该节点从链表中删除。以下是代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None, prev=None):
self.val = val
self.next = next
self.prev = prev
def delete_duplicates(head: ListNode) -> ListNode:
if not head:
return head
visited = set()
visited.add(head.val)
curr = head.next
while curr:
if curr.val in visited:
prev = curr.prev
prev.next = curr.next
if curr.next:
curr.next.prev = prev
else:
visited.add(curr.val)
curr = curr.next
return head
```
在这个算法中,我们首先创建一个哈希表 `visited`,用来记录已经出现的节点值。我们遍历链表,如果当前节点的值已经在哈希表中出现过了,就将该节点从链表中删除。否则,将当前节点的值添加到哈希表中。
这个算法的时间复杂度为 $O(n)$,其中 $n$ 是链表中节点的数量。空间复杂度也为 $O(n)$,因为我们需要使用哈希表来记录已经出现的节点值。