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