两个有序链表合并（新表不含重复元素）

### 回答1：
将两个有序链表合并成一个新的有序链表，新表中不含重复元素。

具体步骤如下：

1. 定义一个新的链表，用于存储合并后的结果。

2. 分别遍历两个有序链表，比较当前节点的值大小，将较小的节点插入到新链表中。

3. 如果两个节点的值相等，则只将其中一个节点插入到新链表中。

4. 遍历完其中一个链表后，将另一个链表剩余的节点全部插入到新链表中。

5. 返回新链表即为合并后的结果。

示例代码如下：

class ListNode:
    def __init__(self, val=, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    cur = dummy
    while l1 and l2:
        if l1.val < l2.val:
            cur.next = ListNode(l1.val)
            l1 = l1.next
        elif l1.val > l2.val:
            cur.next = ListNode(l2.val)
            l2 = l2.next
        else:
            cur.next = ListNode(l1.val)
            l1 = l1.next
            l2 = l2.next
        cur = cur.next
    cur.next = l1 if l1 else l2
    return dummy.next

### 回答2：
题目描述：

给定两个有序单链表，合并成一个没有重复元素的有序单链表。

解题思路：

此题是典型的链表合并问题。本题合并过程建议使用递归。

具体思路如下：

首先判断两个链表是否为空，若都为空则合并结果就是空链表。

若其中一个链表为空，则合并结果就是非空链表。其实也就是把非空链表原封不动地接在新表后面即可。

若两个链表都非空，比较当前两个链表头结点的大小关系。

若链表1的头结点小于等于链表2的头结点，则将链表1的头部节点作为新链表的头节点，并将链表1的子链表和链表2合并。

若链表2的头结点小于链表1的头结点，则将链表2的头部节点作为新链表的头节点，并将链表1的子链表和链表2合并。

由于链表的操作是一循环递归下去就不停的拼接，合并完链表之后就可以直接返回结果头节点。

代码实现：

// 定义链表节点
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2; // l1为空，返回l2链表
if (!l2) return l1; //l2为空，返回l1链表
//比较头结点
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2); //把l1的子链表和l2合并
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next); //把l2的子链表和l1合并
return l2;
}
}
};

如果题目要求的是不需要递归，而需要迭代实现合并有序链表，则可以采用双指针法进行实现：

class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode *tail = &dummy;
while (l1 && l2) { //当两个链表都非空的时候
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else if (l1->val == l2->val) { //包含重复的情况
tail->next = l1;
l1 = l1->next;
l2 = l2->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2; //将未被处理完的链表添加到tail的后面
return dummy.next;
}
};

### 回答3：
有序链表合并是一道非常经典的链表问题，也是面试中比较常见的考察点。

对于这道题目，我们可以使用两个指针分别指向两个有序链表的头节点，然后从头节点开始依次遍历两个链表，比较当前节点的大小，将较小的节点插入到新链表中，直到遍历完其中一个链表。此时，我们只需要将剩余链表连接到新链表的末尾即可。

值得注意的是，在合并时需要注意去重。对于连续相同的元素，我们只需要保留一个即可。因此，在比较大小时，需要判断当前节点和上一个节点是否相同，如果相同则跳过当前节点，继续比较下一个节点。随着链表的不断合并，新链表中不含有重复元素的条件也就得以满足。

下面是具体的代码实现：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (l1 == NULL) {
        return l2;
    }
    if (l2 == NULL) {
        return l1;
    }
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = 0;
    head->next = NULL;
    struct ListNode* cur = head;
    struct ListNode* p1 = l1;
    struct ListNode* p2 = l2;
    while (p1 != NULL && p2 != NULL) {
        if (p1->val == p2->val) {
            p1 = p1->next;
            p2 = p2->next;
            continue;
        }
        if (p1->val < p2->val) {
            cur->next = p1;
            p1 = p1->next;
        } else {
            cur->next = p2;
            p2 = p2->next;
        }
        cur = cur->next;
    }
    cur->next = p1 ? p1 : p2;
    return head->next;
}

这里我们采用了虚拟头节点的方式，使代码实现更加简洁高效。具体实现方式就是创建一个值为0，且next指针为NULL的头节点，然后将新节点插入到其后。这样做的好处是，在链表的头部操作和尾部操作上尤为方便，无需特判。