合并两个排序链表中定义头节点为什么用new

删除合并一个有序链表中的重复节点可以分为两步：首先合并两个已排序链表，然后遍历合并后的链表删除重复节点。这里有一个简单的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)); newNode->val = val; newNode->next = NULL; return newNode; } // 合并两个有序链表 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1->val <= l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } } // 删除链表中的重复节点 ListNode* deleteDuplicates(ListNode* head) { if (!head || !head->next) return head; ListNode* current = head; ListNode* runner = head->next; while (runner) { if (current->val == runner->val) { runner = runner->next; free(current); // 删除当前节点 current = runner; } else { current = current->next; runner = runner->next; } } return head; } // 打印链表 void printList(ListNode* node) { while (node != NULL) { printf("%d -> ", node->val); node = node->next; } printf("NULL\n"); } int main() { // 示例链表：1->1->2->3->3->4 ListNode* l1 = createNode(1); l1->next = createNode(1); l1->next->next = createNode(2); l1->next->next->next = createNode(3); l1->next->next->next->next = createNode(3); l1->next->next->next->next->next = createNode(4); ListNode* mergedList = mergeTwoLists(l1, l1->next->next); // 先合并l1 mergedList = deleteDuplicates(mergedList); // 然后删除重复 printList(mergedList); // 输出: 1 -> 2 -> 3 -> 4 -> NULL return 0; }

合并两个已排序的链表（Merge Two Sorted Lists）是一个经典的链表操作问题，在C++中，可以采用迭代或者递归的方式来解决。这里我们提供一种常见的迭代方法： ```cpp #include <iostream> using namespace std; // 定义链表节点结构 struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // 初始化结果头结点和指针 ListNode* dummy = new ListNode(0); // 创建一个虚拟头节点 ListNode* tail = dummy; // 尾部指针指向虚拟头节点 // 当任一链表未结束时 while (l1 && l2) { // 如果l1的值小于l2的值，则将l1插入到结果链表 if (l1->val < l2->val) { tail->next = l1; l1 = l1->next; } else { // 否则将l2插入 tail->next = l2; l2 = l2->next; } tail = tail->next; // 更新tail指向下个位置 } // 如果其中一个链表已结束，将另一个链表剩余部分添加到结果链表 if (l1) { tail->next = l1; } else { tail->next = l2; } return dummy->next; // 返回合并后的实际头节点 } int main() { ListNode* l1 = new ListNode(1); l1->next = new ListNode(2); l1->next->next = new ListNode(4); ListNode* l2 = new ListNode(1); l2->next = new ListNode(3); l2->next->next = new ListNode(4); ListNode* result = mergeTwoLists(l1, l2); // 打印合并后的链表元素 while (result) { cout << result->val << " "; result = result->next; } return 0; } ```