设ha和hb分别是两个带头结点的非递减有序单链表头指针，试设计一个算法，将这两个有序链表合并成一个非递减有序的单链表。要求结果链仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的

节点。

算法思路：

1. 定义三个指针p、q、r，分别指向ha、hb、合并后的链表的当前节点。

2. 比较p和q指向的节点的值，将较小的节点插入到合并后的链表中，并将指针后移。

3. 如果p或q指向的节点为空，则将另一个链表中剩余的节点全部插入到合并后的链表中。

4. 返回合并后的链表的头指针。

算法实现：

Node* merge(Node* ha, Node* hb) {
    Node* p = ha->next;
    Node* q = hb->next;
    Node* r = ha;
    while (p && q) {
        if (p->data <= q->data) {
            r->next = p;
            p = p->next;
        } else {
            r->next = q;
            q = q->next;
        }
        r = r->next;
    }
    r->next = p ? p : q;
    return ha;
}

算法分析：

时间复杂度为O(n)，其中n为两个链表的节点总数。空间复杂度为O(1)，因为只使用了常数个指针变量。