This is the 18th day of my participation in the August Genwen Challenge.More challenges in August

Merges two ordered lists

Topic describes

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.

The sample

Example 1:

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

Example 2:

Input: L1 = [], L2 = [] output: []

Example 3:

Input: L1 = [], L2 = [0] output: [0]

 

prompt

  • The number of nodes in two linked lists ranges from 0 to 50.
  • -100 <= Node.val <= 100
  • Both L1 and L2 are arranged in non-decreasing order

Thought analysis

We can use iterative method to implement the above algorithm.

When both L1 and L2 are not empty linked lists, judge which of the first nodes in l1 and L2 has a smaller value, and add the node with the smaller value to the result. When a node is added to the result, move the node in the corresponding linked list one bit later.

algorithm

First, we set up a sentinel node pre, which makes it easier to return to the merged list at the end. We maintain a pre pointer, and all we need to do is adjust its next pointer. Then, we repeat the process until l1 or L2 points to null: if the value of l1 current is less than or equal to L2, we append the current l1 node to the pre node and move the l1 pointer back one bit. Otherwise, we do the same for L2. Regardless of which element we appending, we need to move the prev one bit back.

At the end of the loop, at most one of L1 and L2 is non-null. Since both input lists are ordered, no matter which list is non-empty, it contains all the elements larger than all of the previously merged lists. This means that we simply appending the non-empty list to the merged list and return the merged list.

Code implementation

class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode listnode = new ListNode(0); // create a new list ListNode pre = ListNode; if(l1 == null && l2 ==null){ pre.next = null; return pre.next; } while(l1 ! = null && l2 ! = null){ if(l2.val >= l1.val){ pre.next = l1; pre = pre.next; l1 = l1.next; } else { pre.next = l2; pre = pre.next; l2 = l2.next; If (l1 == null){pre.next = l2; } else { pre.next = l1; } return listnode.next; }}Copy the code

The last

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

Welcome to provide new ideas