Detailed explanation of merging ordered linked lists in JavaScript

For the problem of merging two ordered linked lists into one ordered linked list, a classic algorithm is used in Yan Weimin's version of "Data Structure".

1. Use two pointers to point to the nodes currently to be compared in the two linked lists, and create a new linked list to store the nodes in the two linked lists.

2. Each time the size of the node element is compared, the smaller element node is introduced into the new linked list, and the pointer is moved backward. This process continues until one of the pointers is empty.

3. Point another non-null pointer to the remaining part of the linked list, and after linking to the new linked list, the merging process is completed.

This algorithm is very efficient and is O(m+n), but it requires creating a new linked list.

Suppose I have such a requirement:

1. Merge the second linked list into the first linked list, requiring that no new linked list can be generated.

2. The reference relationship of the second linked list node cannot be changed, or in other words, it cannot affect the second linked list.

how should I do it?

Regarding this problem, there are 3 points of analysis:

1. This is a method of inserting elements of the second linked list into the first linked list question.

2. The inserted node cannot be the original node of the second linked list, but a new node, otherwise it will affect the second linked list.

3.The outer loop controls the traversal of the second linked list, and the inner loop is responsible for inserting new nodes, so it is an algorithm of O(m*n).

Specific implementation:

//将l2合并到l1
var mergeTwoLists = function(l1, l2) {
	//遍历l2链表，将元素一一插入l1
    while(l2){
		//先前的l1元素
        var prev = null;
		//当前的l1元素
        var cur = l1;
		//遍历l1链表，找到可插入l2元素的位置
        while(cur && l2.val > cur.val){
			//记录先前的l1元素
            prev = cur;
			//记录当前的l1元素
            cur = cur.next;
        }
		//生成新的节点
		//注意：并没有利用l2已有的节点
        var newNode = new ListNode(l2.val);
		//插入新节点
		//新节点的next指向当前的l1元素
        newNode.next = cur;
		//如果是在l1链表中间插入
		//或者说新节点有前驱
        if(prev){
			//先前元素的next指向新节点
            prev.next = newNode;
        }//如果新节点插在链表头部
        else{
            l1 = newNode;
        }
        l2 = l2.next;
    }
	//返回l1
    return l1;
};

The above is the detailed content of Detailed explanation of merging ordered linked lists in JavaScript. For more information, please follow other related articles on the PHP Chinese website!