Original link: leetcode-cn.com/problems/me…

Answer:

The realization idea refers to the official problem solution.

  1. Traverse two linked lists simultaneously with a double pointer.
  2. When l1.val
  3. When l2.val
  4. When l1.val=l2.val, place L1 and L2 in the new list, respectively, and move l1 and L2 forward one bit
  5. Exit the loop when either list has finished iterating.
  6. At this point, the nodes in the other linked list must be larger than the new list and ordered. It is only necessary to link the new list with the nodes in the remaining linked list.
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var mergeTwoLists = function (l1, l2) {
  // Create a pseudo-node, and the first node of the sorted list will be stored in dummyNode.next
  let dummyNode = new ListNode(-1);
  // The node that stores the new list is reassigned as the new list joins
  // The first node of the new linked list is stored as dummyNode to avoid the problem that the first node is empty when storing the new linked list
  let newListNode = dummyNode;

  // The list is traversed only when both lists have nodes.
  // When a list has been traversed, it is only necessary to join another list after the new list
  while (l1 && l2) {
    // Compare the values of the two nodes and join the nodes with the smaller values to the new list
    if (l1.val <= l2.val) {
      newListNode.next = l1;
      l1 = l1.next;
    } else {
      newListNode.next = l2;
      l2 = l2.next;
    }
    newListNode = newListNode.next;
  }

  // When exiting the loop, connect the list that still has nodes directly to the new list.
  newListNode.next = l1 ? l1 : l2;

  // dummyNode.next points to the first node of the new list
  // The new list is returned.
  return dummyNode.next;
};
Copy the code