JavaScript에서 정렬된 연결 목록 병합에 대한 자세한 설명

두 개의 순서 연결 목록을 하나의 순서 연결 목록으로 병합하는 문제의 경우 Yan Weimin의 "데이터 구조" 버전에서 고전적인 알고리즘이 사용됩니다.

1. 두 개의 포인터를 사용하여 현재 두 연결 리스트에서 비교할 노드를 가리키고, 두 연결 리스트에 노드를 저장하기 위해 새 연결 리스트를 만듭니다.

2. 노드 요소의 크기를 비교할 때마다 더 작은 요소 노드가 새 연결 목록에 도입되고 포인터 중 하나가 비어 있을 때까지 이 프로세스가 계속됩니다.

3. null이 아닌 다른 포인터를 연결 목록의 나머지 부분에 가리키고 새 연결 목록에 연결하면 병합 프로세스가 완료됩니다.

이 알고리즘은 매우 효율적입니다. O(m+n)이지만 새 연결 목록을 만들어야 합니다.

다음과 같은 요구 사항이 있다고 가정해 보겠습니다.

1. 두 번째 연결 목록을 첫 번째 연결 목록에 병합하여 새 연결 목록을 생성할 수 없도록 합니다.

2. 두 번째 연결 리스트 노드의 참조 관계는 변경할 수 없습니다. 즉, 두 번째 연결 리스트에 영향을 미칠 수 없습니다.

어떻게 해야 할까요?

이 문제에 대한 분석 포인트는 3개 있습니다:

1. 첫 번째 연결리스트 질문입니다.

2. 삽입된 노드는 두 번째 연결 리스트의 원래 노드일 수 없으며 새 노드일 수 없습니다. 그렇지 않으면 두 번째 연결 리스트에 영향을 미칩니다.

3.외부 루프는 두 번째 연결 리스트의 순회를 제어하고, 내부 루프는 새 노드 삽입을 담당하므로 O(m*n)의 알고리즘입니다. .

상세 구현:

//将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;
};

위 내용은 JavaScript에서 정렬된 연결 목록 병합에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!