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

算法思路：

1. 找到ha的尾结点，然后将其指向hb的第一个结点；
2. 返回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一次。

相关问题

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

算法步骤如下：

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

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

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

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

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

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

算法思路：

1. 遍历链表ha，找到最后一个节点p1，将p1的next指针指向hb的第一个节点；
2. 返回ha的头节点作为连接后链表的头节点hc。

时间复杂度：O(m)，其中m为ha的长度。

Python代码实现：

def connect_lists(ha, hb):
    """
    将两个单链表连接在一起
    """
    p = ha
    while p.next:
        p = p.next
    p.next = hb
    return ha