单链表a和单链表b有共同结点。设计找出两个链表第一个共同结点的算法,且该算法的时间复杂度为o(n+m),其中n是链表a的长度,m是链表b的长度
时间: 2023-08-31 09:21:02 浏览: 47
### 回答1:
可以先分别遍历两个链表,得到它们的长度n和m。然后让较长的链表先走n-m步,这样两个链表就剩下相同长度了。接着同时从头开始遍历两个链表,直到找到第一个相同的结点为止,即为它们的第一个共同结点。
具体实现如下:
```
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = 0, lenB = 0;
ListNode *curA = headA, *curB = headB;
//分别遍历两个链表,得到它们的长度n和m
while (curA) {
lenA++;
curA = curA->next;
}
while (curB) {
lenB++;
curB = curB->next;
}
//让较长的链表先走n-m步
curA = headA;
curB = headB;
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++) curA = curA->next;
} else {
for (int i = 0; i < lenB - lenA; i++) curB = curB->next;
}
//同时从头开始遍历两个链表,直到找到第一个相同的结点为止
while (curA && curB) {
if (curA == curB) return curA;
curA = curA->next;
curB = curB->next;
}
return nullptr;
}
```
### 回答2:
首先,我们可以先遍历链表a,将链表a的所有节点插入一个哈希表中。然后再遍历链表b,查找每个节点是否在哈希表中出现过。如果找到第一个在哈希表中出现的节点,则该节点就是链表a和链表b的第一个共同结点。
该算法的时间复杂度为O(n+m),其中n是链表a的长度,m是链表b的长度。遍历链表a需要O(n)的时间,将链表a的所有节点插入哈希表需要O(n)的时间。遍历链表b需要O(m)的时间,查找链表b的每个节点在哈希表中是否出现过需要O(m)的时间。
以下是该算法的示例代码:
```python
# 定义链表节点
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
hashset = set() # 创建哈希表
# 遍历链表a,将所有节点插入哈希表
while headA:
hashset.add(headA)
headA = headA.next
# 遍历链表b,查找节点是否在哈希表中出现过
while headB:
if headB in hashset:
return headB
headB = headB.next
return None # 若没有共同结点,则返回None
```
该算法利用哈希表的查找时间复杂度为O(1),因此总的时间复杂度为O(n+m)。
### 回答3:
一个简单的思路是,先遍历链表a,将a中的每个结点存储在一个集合中。然后遍历链表b,对于b中的每个结点,判断该结点是否在集合中,如果在,则该结点即为两个链表的第一个共同结点。
这种算法的时间复杂度是O(n+m),其中n是链表a的长度,m是链表b的长度。
具体实现如下:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_first_common_node(headA, headB):
node_set = set()
current = headA
while current:
node_set.add(current)
current = current.next
current = headB
while current:
if current in node_set:
return current
current = current.next
return None
# 构造测试链表
a = ListNode(1)
a.next = ListNode(2)
a.next.next = ListNode(3)
a.next.next.next = ListNode(6)
a.next.next.next.next = ListNode(7)
b = ListNode(4)
b.next = ListNode(5)
b.next.next = ListNode(6)
b.next.next.next = ListNode(7)
# 测试
result = find_first_common_node(a, b)
if result:
print("Found first common node:", result.val)
else:
print("No common node found.")
```
上述代码在两个链表中都遍历了一次,时间复杂度为O(n+m)。并且通过使用集合,可以实现O(1)时间复杂度的判断当前结点是否在集合中。