题目

已知节点结构 Node：
function Node(val) {
    this.val = val;
    this.next = null;
}

给定两个链表n1,n11(见测试用例)
合并两个链表，并以升序排序

测试用例

var n1 = new Node(3);
var n2 = new Node(2);
var n3 = new Node(5);
n1.next = n2;
n2.next = n3;

var n11 = new Node(1);
var n22 = new Node(22);
var n33 = new Node(4);
n11.next = n22;
n22.next = n33;

代码

/**
 * 排序单个链表
 * @param l1
 * @returns {Node|*}
 */
function merge(l1) {
    result = new Node(l1.val);
    l1 = l1.next;
    while (l1) {
        var current = result;
        var before = null;
        while(current) {
            if (current.val < l1.val) {
                if (!current.next) {
                    current.next = new Node(l1.val);
                    break;
                }
            } else {
                if (before === null) {
                    var n = new Node(l1.val);
                    n.next = result;
                    result = n;
                    break;
                } else {
                    before.next = new Node(l1.val);
                    before.next.next = current;
                    break;
                }
            }

            before = current;
            current = current.next;
        }
        l1 = l1.next;
    }

    return result;
}

/**
 * 合并两个链表
 * @param l1
 * @param l2
 * @returns {Node|*}
 */
function towMerge(l1, l2) {
    var r1 = merge(l1);
    var all = r1;
    var r2 = merge(l2);
    var tag = r1;
    while (r1) {
        tag = r1;
        r1 = r1.next;
    }
    tag.next = r2;
    return merge(all);
}

验证

towMerge(n1, n11);