用Python 已知两个单链表的头结点ha和hb,并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后)。假设指针hc指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算。请分析算法的时间复杂度。
时间: 2023-05-30 14:04:56 浏览: 117
试写出一个计算单链表中结点个数的算法,其中指针p指向该链表的第一个结点。
算法思路:
1. 遍历链表ha,找到最后一个节点p1,将p1的next指针指向hb的第一个节点;
2. 返回ha的头节点作为连接后链表的头节点hc。
时间复杂度:O(m),其中m为ha的长度。
Python代码实现:
```python
def connect_lists(ha, hb):
"""
将两个单链表连接在一起
"""
p = ha
while p.next:
p = p.next
p.next = hb
return ha
```
阅读全文