【练习】【链表】力扣热题10021.合并两个有序链表

题目

来源：力扣热题100 21. 合并两个有序链表

---

思路（注意事项） 新建一个头节点，操作。 ListNode* head = new ListNode(0); 此题不用放断链。最终返回链表可以不用删除头节点，直接找到对应的位置返回。

---

纯代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* head = new ListNode(0); ListNode *e = head; while (list1 != nullptr && list2 != nullptr) { if (list1 -> val >= list2 -> val) { e -> next = list2; list2 = list2 -> next; } else { e -> next = list1; list1 = list1 -> next; } e = e ->next; } if (list1 != nullptr) e -> next = list1; if (list2 != nullptr) e -> next = list2; return head -> next; } }; 题解（加注释） /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} // 默认构造函数 * ListNode(int x) : val(x), next(nullptr) {} // 带值的构造函数 * ListNode(int x, ListNode *next) : val(x), next(next) {} // 带值和下一个节点的构造函数 * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { // 创建一个虚拟头节点，方便操作 ListNode* head = new ListNode(0); // 定义一个指针 e，用于遍历新链表 ListNode *e = head; // 遍历两个链表，直到其中一个链表为空 while (list1 != nullptr && list2 != nullptr) { // 比较两个链表当前节点的值 if (list1->val >= list2->val) { // 如果 list2 的当前节点值较小，将其接入新链表 e->next = list2; // 移动 list2 的指针到下一个节点 list2 = list2->next; } else { // 如果 list1 的当前节点值较小，将其接入新链表 e->next = list1; // 移动 list1 的指针到下一个节点 list1 = list1->next; } // 移动新链表的指针到下一个节点 e = e->next; } // 如果 list1 还有剩余节点，将其全部接入新链表 if (list1 != nullptr) e->next = list1; // 如果 list2 还有剩余节点，将其全部接入新链表 if (list2 != nullptr) e->next = list2; // 返回新链表的头节点（跳过虚拟头节点） return head->next; } };