将两个递增的有序链表合并为一个递增的有序链表

将两个递增的有序链表合并为一个递增的有序链表的基本思路是:
1. 创建一个新链表,
2. 比较两个链表的头结点, 将较小的节点插入新链表
3. 将新链表的尾节点指向下一个较小的节点
4. 重复步骤2和3, 直到两个链表都遍历完
5. 将剩余部分直接链接到新链表的尾部

相关问题

将两个递增有序链表合并为一个递增有序链表。要求 1.结果链表仍然使用原来两个链表的存储空间，不占用其它空间 2.表中不许有重复数据用c语言完整写出来

在C语言中，将两个递增有序链表合并为一个新的递增有序链表，并保持原链表的空间不变，可以采用迭代或递归的方式实现。这里提供一个简单的迭代方法：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 合并两个有序链表的函数
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2; // 如果l1为空，直接返回l2
    if (!l2) return l1; // 如果l2为空，直接返回l1

    // 创建新链表头指针
    ListNode* result = (l1->val <= l2->val) ? l1 : l2;

    // 使用临时指针遍历较小值链表
    ListNode* temp = (result != l1) ? l1 : l2;
    while (temp && temp->next) { // 当前链表非空且还有下一个元素
        if (temp->next->val > temp->val) { // 检查是否需要切换到另一个链表
            result->next = (result == l1) ? l2 : l1;
            result = (result == l1) ? temp->next : temp; // 走到下一个最小值
        } else {
            temp = temp->next; // 继续遍历当前链表
        }
    }

    // 链表结束时添加剩余链表
    result->next = (result == l1) ? l2->next : l1->next;

    return result;
}

// 测试函数
void printList(ListNode* head) {
    while (head) {
        printf("%d -> ", head->val);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    // 初始化两个示例链表
    ListNode* l1 = (ListNode*)malloc(sizeof(ListNode));
    l1->val = 1;
    l1->next = (ListNode*)malloc(sizeof(ListNode));
    l1->next->val = 2;
    l1->next->next = NULL;

    ListNode* l2 = (ListNode*)malloc(sizeof(ListNode));
    l2->val = 1;
    l2->next = (ListNode*)malloc(sizeof(ListNode));
    l2->next->val = 3;
    l2->next->next = NULL;

    ListNode* merged = mergeTwoLists(l1, l2);

    printList(merged); // 输出合并后的链表

    free(l1);
    free(l2);
    return 0;
}

将两个递增有序链表合并为一个递增有序链表。要求 // 1.结果链表仍然使用原来两个链表的存储空间，不占用其它空间 // 2.表中不许有重复数据，用c语言完整写出来

将两个递增有序链表合并成一个新的递增有序链表，可以使用迭代的方式解决，同时保持链表原有的内存分配，并避免插入重复元素。下面是一个C语言的解决方案：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct ListNode {
    int val;          // 节点值
    struct ListNode* next;   // 指向下一个节点的指针
} ListNode;

// 创建新节点
ListNode* createNode(int val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (newNode != NULL) {
        newNode->val = val;
        newNode->next = NULL;
    }
    return newNode;
}

// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = createNode(0); // 创建虚拟头节点
    ListNode* tail = dummy;      // 尾节点指向虚拟头

    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    // 如果其中一个链表未遍历完，将其剩余部分添加到结果链表尾部
    if (l1 != NULL)
        tail->next = l1;
    else if (l2 != NULL)
        tail->next = l2;

    return dummy->next; // 返回实际的头部节点
}

// 打印链表
void printList(ListNode* head) {
    while (head != NULL) {
        printf("%d -> ", head->val);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    // 测试示例
    ListNode* l1 = createNode(1);
    l1->next = createNode(2);
    l1->next->next = createNode(4);

    ListNode* l2 = createNode(1);
    l2->next = createNode(3);
    l2->next->next = createNode(4);

    ListNode* result = mergeTwoLists(l1, l2);
    printList(result); // 输出：1 -> 1 -> 2 -> 3 -> 4 -> 4 -> NULL

    return 0;
}

这个程序首先创建一个虚拟头节点，然后通过对比两个链表的当前节点值来决定添加哪一个到结果链表中。最后返回合并后的实际链表头部。