This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

Topic describes

This is 21 on LeetCode. Merging two ordered lists is Easy.

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 to 50.
  • -100 <= Node.val <= 100
  • l1 和 l2All in non-decreasing order

Two-pointer solution (Sentry technique)

We talked about adding two numbers (medium) before, let Mitsuha remind you:

A common technique for linked list problems is to add a virtual head node (sentry) to help simplify boundary cases.

Since the two lists are themselves ordered, they only need to be compared during traversal:

Code:

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;    
        if (l2 == null) return l1;
                
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(l1 ! =null&& l2 ! =null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else{ cur.next = l2; cur = cur.next; l2 = l2.next; }}while(l1 ! =null) {
            cur.next = l1;
            cur = cur.next;
            l1 = l1.next;
        }
        while(l2 ! =null) {
            cur.next = l2;
            cur = cur.next;
            l2 = l2.next;
        }
        
        returndummy.next; }}Copy the code

  • Time complexity: Scan two linked lists once. The complexity is O(n)O(n)O(n)

  • Space complexity: O(1)O(1)O(1)

The last

This is the No.21 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks, so we will finish all the topics without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.