使用python写出：已知两个单链表的头结点ha和hb，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后）。假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析算法的时间复杂度。

算法实现：

遍历ha链表，找到最后一个结点；
将hb链表的头结点连接到ha链表的最后一个结点之后；
返回ha链表的头结点。

时间复杂度为O(m)，其中m为ha链表的长度。
代码实现：
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
登录后复制

相关问题

python已知两个单链表的头结点ha和hb，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后）。假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析算法的时间复杂度。

算法步骤如下：

判断ha和hb是否为空，如果有一个为空则返回另一个链表的头结点。

遍历链表ha，找到其最后一个结点，记为p。

将p的next指针指向hb的头结点，即p->next = hb。

返回ha作为连接后的链表的头结点。

时间复杂度为O(m)，其中m为链表ha的长度，因为需要遍历ha找到其最后一个结点。

python 已知两个单链表的头结点ha和hb，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后）。假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析算法的时间复杂度。

算法思路：

找到ha的尾结点，然后将其指向hb的第一个结点；
返回ha作为新链表的头结点。

算法实现：
def merge_lists(ha, hb):
if not ha:
return hb
if not hb:
return ha
p = ha
while p.next:
p = p.next
p.next = hb
return ha
登录后复制
时间复杂度为O(m)，其中m为ha的长度。因为算法只遍历了ha一次。