单链表找公共结点时间复杂度
时间: 2023-08-10 11:05:54 浏览: 55
单链表找公共结点的时间复杂度是O(m + n),其中m和n分别是两个链表的长度。
要找到两个单链表的公共结点,可以先分别遍历两个链表,得到它们的长度。然后让较长的链表先移动差值个结点,使得两个链表剩余的长度相等。接下来同时遍历两个链表,比较每个结点是否相同,直到找到第一个相同的结点或者遍历到链表的末尾。
由于需要遍历两个链表,所以时间复杂度为O(m + n)。
相关问题
再单链表的某个结点前插入一个新结点和再某个结点后插入一个新结点,时间复杂度有什么不同,为什么
在单链表中,插入一个新结点需要找到插入位置的前驱结点,然后进行插入操作。因此,在某个结点前插入一个新结点和在某个结点后插入一个新结点的时间复杂度是不同的。
在某个结点前插入一个新结点的时间复杂度为O(n),其中n是链表的长度。因为需要遍历链表找到插入位置的前驱结点,最坏情况下需要遍历整个链表。
在某个结点后插入一个新结点的时间复杂度为O(1)。因为只需要修改该结点的指针,将其指向新结点,不需要遍历整个链表。
因此,如果需要频繁地在单链表中进行插入操作,最好选择在某个结点后插入新结点,以减少时间复杂度。
删除单链表的重复结点
可以使用哈希表来实现删除单链表的重复结点。具体步骤如下:
1. 创建一个哈希表,用于存储已经出现过的结点值。
2. 遍历单链表,对于每个结点,判断其值是否已经在哈希表中出现过。
3. 如果该结点的值已经在哈希表中出现过,则将该结点从单链表中删除。
4. 如果该结点的值没有在哈希表中出现过,则将该结点的值加入哈希表中。
代码实现如下:
```python
def remove_duplicates(head):
if not head:
return None
hash_set = set()
hash_set.add(head.val)
pre = head
cur = head.next
while cur:
if cur.val in hash_set:
pre.next = cur.next
else:
hash_set.add(cur.val)
pre = cur
cur = cur.next
return head
```