使用python写出:已知两个单链表的头结点ha和hb,并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后)。假设指针hc指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算。请分析算法的时间复杂度。
时间: 2023-05-29 15:08:06 浏览: 77
算法实现:
1. 遍历ha链表,找到最后一个结点;
2. 将hb链表的头结点连接到ha链表的最后一个结点之后;
3. 返回ha链表的头结点。
时间复杂度为O(m),其中m为ha链表的长度。
代码实现:
```python
def connect_list(ha, hb):
if ha is None:
return hb
if hb is None:
return ha
p = ha
while p.next is not None:
p = p.next
p.next = hb
return ha
```
阅读全文