LeetCode-21合并两个有序链表

题目来源

21. 合并两个有序链表 - 力扣（LeetCode）

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = [] 输出：[]

示例 3：

输入：l1 = [], l2 = [0] 输出：[0]

提示 两个链表的节点数目范围是 [0, 50]-100 <= Node.val <= 100l1 和 l2 均按 非递减顺序 排列

题目解析

本题的要求是：需要使用 list1 和 list2 的节点来构成合并后的链表。

这里我们可以为合并后的链表创建一个虚拟头节点 dummy_head，之后按照下面图示逻辑进行：

C源码实现 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* dummy_head = (struct ListNode*)malloc(sizeof(struct ListNode)); dummy_head->val = 0; dummy_head->next = NULL; struct ListNode* tail = dummy_head; while (list1 != NULL && list2 != NULL) { if (list1->val < list2->val) { tail->next = list1; list1 = list1->next; } else { tail->next = list2; list2 = list2->next; } tail = tail->next; } tail->next = list1 != NULL ? list1 : list2; return dummy_head->next; }

C++源码实现 /** * 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* dummy_head = new ListNode(0, nullptr); ListNode* tail = dummy_head; while (list1 != nullptr && list2 != nullptr) { if (list1->val < list2->val) { tail->next = list1; list1 = list1->next; } else { tail->next = list2; list2 = list2->next; } tail = tail->next; } tail->next = list1 != nullptr ? list1 : list2; return dummy_head->next; } };

Java源码实现 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy_head = new ListNode(0, null); ListNode tail = dummy_head; while (list1 != null && list2 != null) { if (list1.val < list2.val) { tail.next = list1; list1 = list1.next; } else { tail.next = list2; list2 = list2.next; } tail = tail.next; } tail.next = list1 != null ? list1 : list2; return dummy_head.next; } }

Python源码实现 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def mergeTwoLists(self, list1, list2): """ :type list1: Optional[ListNode] :type list2: Optional[ListNode] :rtype: Optional[ListNode] """ dummy_head = ListNode(0, None) tail = dummy_head while list1 != None and list2 != None: if list1.val < list2.val: tail.next = list1 list1 = list1.next else: tail.next = list2 list2 = list2.next tail = tail.next tail.next = list1 if list1 else list2 return dummy_head.next

JavaScript源码实现 /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} list1 * @param {ListNode} list2 * @return {ListNode} */ var mergeTwoLists = function (list1, list2) { const dummy_head = new ListNode(0, null); let tail = dummy_head; while (list1 != null && list2 != null) { if (list1.val < list2.val) { tail.next = list1; list1 = list1.next; } else { tail.next = list2; list2 = list2.next; } tail = tail.next; } tail.next = list1 != null ? list1 : list2; return dummy_head.next; };