21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

题目要求

给定两个有序的链表，把他俩合并成一个有序的链表。

思路

首先明确，这两个链表本身有序，则我们在合并时，一个全部合并完了，另一个直接接到表尾就好了。
创建一个虚拟头结点，指向新表头，即两个head较小的那一个，之后再逐个比较，以此链接下去

代码

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1==null&&l2!=null) {
            return l2;
        }
        if (l2==null&&l1!=null) {
            return l1;
        }
        
        if (l1==null&&l2==null) {
            return l1;
        }
        
        ListNode q1=l1,q2=l2,headr=new ListNode(0);//定义两个指针用于遍历，一个虚拟头结点指向新表头
        if (q1.val<q2.val) {
            headr.next=q1;
            q1=q1.next;
        }else {
            headr.next=q2;
            q2=q2.next;
        }
        ListNode qr =headr.next;//qr用于增加新表
        
        while (q1!=null&&q2!=null) {
            if (q1.val<q2.val) {
                qr.next=q1;
                qr=qr.next;
                q1=q1.next;
            }else {
                qr.next=q2;
                qr=qr.next;
                q2=q2.next;
            }
            
        }
        if (q1!=null) {//即q2为null（都不为空就还在上面循环里了），所以把q1剩下的连接到新表尾部
            qr.next=q1;
        }
        
        if (q2!=null) {
            qr.next=q2;
        }
        
        return headr.next;//返回新表头

    }