21. Merge two ordered lists – LeetCode (leetcode-cn.com)

Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]Copy the code

Example 2:

Input: L1 = [], L2 = [] output: []Copy the code

Example 3:

Input: L1 = [], L2 = [0] output: [0]Copy the code

Tip:

  • The number of nodes in two linked lists ranges from[0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2All pressNondecreasing orderarrangement

Node. val is the value of the current node, and node.next connects to the next node. The specific ideas are as follows: Since the list is already in strict ascending order, we can directly traverse the two lists by defining a root as the result, and then using three Pointers P, P1, and P2 to point to root, L1, and L2 respectively. When neither list is empty,p points to (join) the smaller nodes in P1 and P2. We then move the pointer to both the connected node and root back until one of the lists is empty, and the rest of the list can be directly sprouted on P.ext (all greater than the value of the list where the pointer is already null, in ascending order), and finally return root.next because the first node was null when new ListNode was created. Time complexity o(n), space complexity do not know how to calculate the js implementation of the linked list data structure =_=!!

Code:

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var mergeTwoLists = function(l1, l2) { const root = new ListNode(0) let p = root let p1 = l1 let p2 = l2 while (p1 && p2) { if (p1.val < p2.val) { p.next  = p1 p1 = p1.next } else { p.next = p2 p2 = p2.next } p = p.next } p.next = p1 || p2 return root.next };Copy the code