Nuggets team number online, help you Offer rimmon! Click to see details

I. Topic Description:

Merge the two ascending lists into a new ascending list and return. The new list is formed by concatenating all the nodes of the given two lists.

  • The sample

 

Input: l1 = 4-trichlorobenzene [1], l2 = [1 4] output:,1,2,3,4,4 [1] example 2: input: l1 = [], l2 = [] output: [] example 3: input: l1 = [], l2 = [0] output: [0] tip: The number of nodes in the two linked lists ranges from [0, 50] -100 <= node. val <= 100 l1 and L2 are arranged in non-decreasing orderCopy the code

 

Ii. Thinking analysis:

  • We’re going to use the extended operator and sort it, but we’re not going to pass in a ListNode, not a simple array.
  • Since we are passing in listNodes, we need to determine the values in the two ListNodes and then recursively merge the elements in each ListNode

Three, AC 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) { if (l1 === null) { return l2; } else if (l2 === null) { return l1; } else if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; }}; Status: Elapsed time: 92 ms Memory consumption: 39.4 MBCopy the code

Four,

  • Of course more than one method, also see the official use of iteration;
var mergeTwoLists = function(l1, l2) { const prehead = new ListNode(-1); let prev = prehead; while (l1 ! = null && l2 ! = null) { if (l1.val <= l2.val) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; Next = l1 === null? Next = l1 == null? l2 : l1; return prehead.next; };Copy the code

For reference only

Refer to the topic

  • Force button (LeetCode)