Topic describes
Enter two incrementally sorted lists and merge them so that the nodes in the new list are still incrementally sorted.
Example 1:
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4Copy the code
Limitations:
- 0 <= List length <= 1000
solution
Iterate over both lists at the same time, merge and insert into the new list.
Python3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
p = dummy
while l1 and l2:
if l1.val <= l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
p.next = l1 or l2
return dummy.next
Copy the code
Java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode p = dummy; while (l1 ! = null && l2 ! = null) { if (l1.val <= l2.val) { p.next = l1; l1 = l1.next; } else { p.next = l2; l2 = l2.next; } p = p.next; } p.next = l1 == null ? l2 : l1; return dummy.next; }}Copy the code
JavaScript
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var mergeTwoLists = function (l1, 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(l2.next, l1); return l2; }};Copy the code
C++
class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (nullptr == l1 && nullptr == l2) { return nullptr; / / is empty, both are returned directly} the if (nullptr = = l1 | | nullptr = = l2) {return l1 = = nullptr? l2 : l1; } ListNode* node = nullptr;} ListNode* node = null; if (l1->val > l2->val) { node = l2; node->next = mergeTwoLists(l1, l2->next); } else { node = l1; node->next = mergeTwoLists(l1->next, l2); } return node; }};Copy the code