Merge Two Sorted Lists

Easy

Python

def merge_two_lists(l1,l2):
    dummy=type('N',(),{'val':0,'next':None})()
    cur=dummy
    while l1 and l2:
        if l1.val<=l2.val: cur.next=l1; l1=l1.next
        else: cur.next=l2; l2=l2.next
        cur=cur.next
    cur.next=l1 or l2
    return dummy.next

Java

public ListNode mergeTwoLists(ListNode l1,ListNode l2){
    ListNode dummy=new ListNode(0),cur=dummy;
    while(l1!=null&&l2!=null){
        if(l1.val<=l2.val){cur.next=l1;l1=l1.next;}
        else{cur.next=l2;l2=l2.next;}
        cur=cur.next;
    } cur.next=l1!=null?l1:l2;
    return dummy.next;
}

Key Insight

Python 'l1 or l2' returns first truthy. Java needs ternary.

Python → Java Differences

while l1 and l2 vs !=null
l1 or l2 returns first non-None
Java ternary null check

Python

def merge_two_lists(l1,l2):
    dummy=type('N',(),{'val':0,'next':None})()
    cur=dummy
    while l1 and l2:
        if l1.val<=l2.val: cur.next=l1; l1=l1.next
        else: cur.next=l2; l2=l2.next
        cur=cur.next
    cur.next=l1 or l2
    return dummy.next

Java

public ListNode mergeTwoLists(ListNode l1,ListNode l2){
    ListNode dummy=new ListNode(0),cur=dummy;
    while(l1!=null&&l2!=null){
        if(l1.val<=l2.val){cur.next=l1;l1=l1.next;}
        else{cur.next=l2;l2=l2.next;}
        cur=cur.next;
    } cur.next=l1!=null?l1:l2;
    return dummy.next;
}

Algorithm Steps

1. Dummy head
2. Compare and link smaller
3. Attach remaining

← Previous All Linked Lists Next →