[剑指offer刷题] Acwing 36 合并两个排序的链表（双指针）

单纯的双指针，容易想，简单

class Solution {
    public ListNode merge(ListNode l1, ListNode l2) {

        if (l1 == null && l2 == null) return null;

        if (l1 == null && l2 != null) return l2;
        if (l1 != null && l2 == null) return l1;

        ListNode t1 = l1, t2 = l2;
        ListNode res = null;
        if (t1.val < t2.val) {
            res = t1;
            t1 = t1.next;
        }
        else {
            res = t2;
            t2 = t2.next;   
        }

        ListNode t0 = res;

        while (t1 != null && t2 != null) {
            if (t1.val < t2.val) {
                res.next = t1;
                t1 = t1.next; 
                res = res.next;
            } else {
                res.next = t2;
                t2 = t2.next;
                res = res.next;
            }
        }

        while (t1 != null) {
            res.next = t1;
            t1 = t1.next;
            res = res.next;
        }

        while (t2 != null) {
            res.next = t2;
            t2 = t2.next;
            res = res.next;
        }
        return t0;
    }
}

2. 使用虚拟节点，代码更短

class Solution {
    public ListNode merge(ListNode l1, ListNode l2) {

        ListNode dummy = new ListNode(-1);
        ListNode t1 = l1, t2 = l2;
        ListNode cur = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next; 
                cur = cur.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
                cur = cur.next;
            }
        }

        if (l1 != null) cur.next = l1;
        else cur.next = l2;
        return dummy.next;
    }
}