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

算法思路：

首先找到链表A的尾节点，将其指向链表B的头节点，即可完成链表连接操作。

算法实现：

def connectLinkedList(ha, hb):
    # 找到链表A的尾节点
    p = ha
    while p.next:
        p = p.next
    # 将链表B连接在尾节点后面
    p.next = hb.next
    return ha

时间复杂度为$O(m)$，其中$m$为链表A的长度。

相关问题

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，找到最后一个节点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