数据结构题目22：合并成一个按值有序链接的线性链表将两个按值有序

题目：将两个按值有序链表的非空线性链表合并成一个按值有序链接的线性链表
解题思路：设lista和listb分别为两个有序链表的第1个链结点的指针。将这两个有序链表合并为一个有序链表，并设合并后的链表的第1个链结点的指针为listc。
这里，只需设置3个指针p,q,r。其中，p和q分别指向链表lista和listb当前待比较插入的链结点，而r指向链表listc中当前最后那个链结点。然后不断比较p与q所指的链结点的数据域值，若p->data小于q->data，则将p所指链结点连接到r所指的链结点之后，否则将q所指的链结点链接到r所指的链结点之后。当其中一个链表为空时，只需将另一个链表中剩余的链结点都依次链接到r所指的链结点之后即可。初始时，让listc指向lista和listb所指的链结点中值小的那一个链结点。
具体算法实现如下：

function mergeList(lista ,listb) {
    let listc, p=lista, q=listb, r
    if ( lista.data < listb.data) {
        listc = lista
        r = lista
        p = lista.link
    } else {
        listc = listb
        r = listb
        q = listb.link
    }
    while( p!=null && q!=null ){
        if ( p.data <= q.data) {
            r.link = p
            r = p
            p = p.link
        } else {
            r.link = q
            r = q
            q = q.link
        }
    }
    r.link = p ? p : q
    return listc
}

function createLinklist1(n) {
    let p, r, list = null
    let a , i
    for ( i=1; i<=n; i++) {
        a = i*2 //获取一个数据元素
        p = new Node(a, null) //申请一个新的链结点，data赋值，指针域置空
        if (list==null) {
            list = p
        } else {
            r.link = p
        }
        r = p
    }
    return list
}
function createLinklist2(n) {
    let p, r, list = null
    let a , i
    for ( i=1; i<=n; i++) {
        a = i //获取一个数据元素
        p = new Node(a, null) //申请一个新的链结点，data赋值，指针域置空
        if (list==null) {
            list = p
        } else {
            r.link = p
        }
        r = p
    }
    return list
}
var lista = createLinklist1(5)
console.log('创建的list为：', toString(lista))
var listb = createLinklist2(5)
console.log('创建的list为：', toString(listb))

var r_list = mergeList(lista, listb)
console.log('合并后的链表为：', toString(r_list))