假设有两个按元素值非递减次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值非递增次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

### 回答1：
算法步骤如下：

1. 定义三个指针：p1指向第一个单链表的头结点，p2指向第二个单链表的头结点，p3指向归并后的单链表的头结点（初始为空）。

2. 比较p1和p2指向的结点的值，将较小的结点插入到p3所指向的单链表的末尾，并将p3指向新插入的结点。

3. 重复步骤2，直到p1或p2指向的结点为空。

4. 将p1或p2指向的剩余结点插入到p3所指向的单链表的末尾。

5. 返回归并后的单链表的头结点。

算法实现如下：

// 定义单链表结点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode dummy(); // 定义虚拟头结点
    ListNode* p1 = l1;
    ListNode* p2 = l2;
    ListNode* p3 = &dummy;
    while (p1 && p2) {
        if (p1->val <= p2->val) {
            p3->next = p1;
            p1 = p1->next;
        } else {
            p3->next = p2;
            p2 = p2->next;
        }
        p3 = p3->next;
    }
    if (p1) p3->next = p1;
    if (p2) p3->next = p2;
    return dummy.next;
}

### 回答2：
本题要求将两个按元素值非递减次序排列的单链表，即两个已经排好序的单链表，归并为一个按元素值非递增次序排列的单链表，并且要求利用原来两个单链表的结点存放归并后的单链表。

首先可以考虑从头节点开始比较两个单链表的元素值，将较小的结点插入一个新的单链表中，直到两个单链表其中之一为空。然后剩下的单链表的结点，可以直接插入到新的单链表中，因为根据题意两个单链表已经是按照元素值升序排列了。

不过，在这个基本的合并思路上，需要特别注意两个单链表中相同元素的情况，因为题目要求归并后的单链表按元素值非递增次序排列，所以要将相同元素插入到逆序链表的第一个结点之前。

算法具体步骤如下：

1. 定义一个新的单链表，作为归并后的单链表头节点，设为head。
2. 定义两个指针p1，p2，分别指向两个单链表的头结点。
3. 判断p1和p2指向的结点，将较小的结点插入到链表head的头结点之后，同时指针后移。
4. 判断p1和p2是否都为空，如果有一个为空，跳过步骤5，否则回到步骤3。
5. 如果p1和p2都为空，处理完毕，返回head；否则，将非空链表直接插入到链表head的头结点之后。
6. 反转链表head。
7. 返回head。

具体实现可以参考下列示例代码：

# 定义单链表结点
class Node:
    def __init__(self, val=None):
        self.val = val
        self.next = None

# 定义链表类
class LinkedList:
    def __init__(self):
        self.head = None
        
    # 添加结点
    def add(self, val):
        node = Node(val)
        if self.head is None:
            self.head = node
        else:
            cur = self.head
            while cur.next is not None:
                cur = cur.next
            cur.next = node
            
    # 反转链表
    def reverse(self):
        if self.head is None or self.head.next is None:
            return self.head
        pre = None
        cur = self.head
        while cur is not None:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        self.head = pre

# 定义算法函数，合并两个有序单链表，并且生成一个非递减次序排列的单链表
def mergeLinkedList(l1, l2):
    # 定义头结点为None的单链表
    head = LinkedList()

    # 定义指针，分别从两个链表头结点开始遍历
    p1 = l1.head
    p2 = l2.head

    # 比较元素大小，并将较小的插入到新的单链表中
    while p1 is not None and p2 is not None:
        if p1.val <= p2.val:
            node = Node(p1.val)
            p1 = p1.next
        else:
            node = Node(p2.val)
            p2 = p2.next
        node.next = head.head.next
        head.head.next = node

    # 将非空链表直接插入到新的单链表中
    while p1 is not None:
        node = Node(p1.val)
        node.next = head.head.next
        head.head.next = node
        p1 = p1.next
    while p2 is not None:
        node = Node(p2.val)
        node.next = head.head.next
        head.head.next = node
        p2 = p2.next

    # 将新的单链表反转为非递增次序，并返回
    head.reverse()
    return head

时间复杂度分析：

合并两个单链表的时间复杂度为O(m+n)，其中m和n分别是两个单链表的长度。反转链表的时间复杂度为O(n)。所以总时间复杂度为O(m+n)。因为算法没有使用额外的空间，所以空间复杂度为O(1)。

### 回答3：
这是一道经典的合并链表的问题。我们可以从头节点开始逐个比较两个链表的元素值，将较小的那个加入结果链表中，并且将它所在的链表的头指针指向下一个节点。直到其中一个链表为空，我们就合并完成了。最后，我们需要判断哪个链表还有剩余元素，将剩余元素全部加入结果链表中即可。

假设两个链表分别为L1和L2，归并后的结果链表为L3。算法流程如下：

1.初始化指针p1和p2，分别指向L1和L2的头节点。
2.比较p1和p2指向的元素值，将较小的那个加入结果链表L3中。然后将较小元素所在的链表的头指针指向下一个节点。
3.重复步骤2，直到L1或L2为空。
4.判断哪个链表还有剩余元素，将剩余元素全部加入结果链表L3中。
5.返回L3。

注意，在将元素添加到L3时，要将其按照非递增次序排列。因此，我们需要在添加元素时，寻找它在L3中的插入位置。这可以通过在L3中遍历元素来实现。

以下是具体的实现：

/* 将L1和L2归并为一个非递增次序排列的链表，合并结果存放在L1中 */
void MergeList(LinkList& L1, LinkList L2) {
    if (L1 == nullptr) {
        L1 = L2;
        return;
    }
    if (L2 == nullptr) {
        return;
    }

    LinkList p1 = L1, p2 = L2;
    LinkList pre = nullptr, next = nullptr;
    while (p1 != nullptr && p2 != nullptr) {
        if (p1->data <= p2->data) {
            pre = p1;
            p1 = p1->next;
        } else {
            next = p2->next;
            p2->next = p1;
            if (pre == nullptr) {
                L1 = p2;
            } else {
                pre->next = p2;
            }
            p1 = p2;
            p2 = next;
        }
    }

    if (p2 != nullptr) {
        pre->next = p2;
    }
}

以上算法的时间复杂度为$O(n)$，其中$n$为L1和L2的元素总数。空间复杂度为$O(1)$，因为它只需要利用原来两个单链表的结点存放归并后的单链表。