Subject to introduce

Force buckle 21: leetcode-cn.com/problems/me…

Analysis of the

I will give you two ordered lists and ask you to combine them into a new ordered list. The function signature is as follows:

ListNode mergeTwoLists(ListNode l1, ListNode l2);
Copy the code

This one is relatively easy, so let’s go straight to the solution:

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }} * * /
class Solution {
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // virtual header
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        ListNode p1 = l1, p2 = l2;

        while(p1 ! =null&& p2 ! =null) {
            // Compare Pointers P1 and p2
            // connect nodes with smaller values to the p pointer
            if(p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            }else {
                p.next = p2;
                p2 = p2.next;
            }
            // the p pointer keeps advancing
            p = p.next;
        }
        
        // If l1 has not been traversed, concatenate directly after p
        if(p1 ! =null) {
           p.next = p1; 
        }
        
        // If l2 has not been traversed, concatenate directly after p
        if(p2 ! =null) {
           p.next = p2; 
        }
        returndummy.next; }}Copy the code

Our while loop compares p1 and p2 each time, joining the smaller nodes to the result list:

The logic of this algorithm is similar to “zipper zipper”, L1 and L2 are similar to the zigzag on both sides of the zipper, and pointer P is like the zipper’s cable, which merges two ordered linked lists.

The code also uses a linked list algorithm that is very common in the “dummy head node” technique, also known as dummy node. Dummy nodes are placeholders that reduce code complexity by avoiding null Pointers.