흥미로운 JavaScript 질문: 일종의 연결 목록 병합

병합 정렬은 먼저 나누고 합치는 과정이라는 것을 다들 아셔야 합니다.

그렇다면 단일 연결 목록을 병합 정렬하려면 어떻게 해야 할까요?

먼저 다음 의사 코드와 같이 연결 목록을 분할하는 방법이 필요합니다.

var source = 1 -> 3 -> 7 -> 8 -> 11 -> 12 -> 14 -> null  
var front = new Node()  
var back = new Node()  
frontBackSplit(source, front, back)  
front === 1 -> 3 -> 7 -> 8 -> null  
back === 11 -> 12 -> 14 -> null

연결 목록의 꼬리 포인터를 매개변수로 받아 연결 목록을 다음으로 분할합니다. two , 즉 전반부와 후반부입니다.

그럼 이 중간 컷오프 값은 어떻게 결정하나요?

빠른 포인터와 느린 포인터를 동시에 사용할 수 있으며, 빠른 포인터는 꼬리에서 동시에 시작하여 단일 연결 리스트를 탐색합니다. 빠른 포인터는 매번 2단계를 수행하고 느린 포인터는 1단계를 수행합니다. 그러면 빠른 포인터가 확실히 끝에 먼저 도달할 것이고 느린 포인터는 이때 이동 거리의 절반만 이동한 것입니다. 즉, 느린 포인터는 정확히 이 분할 위치에 있습니다.

나머지는 다루기 쉽고, 경계선을 잘라내고, 설정을 null로 설정하면 첫 번째 단계가 완료됩니다.

function Node(data) {  
    this.data = data === undefined ? null : data;  
    this.next = null;  
}  
  
function frontBackSplit(source, front, back) {  
    var total = 0;  
    var fast = source;  
    var slow = source;  
    var partial = null;  
    while(fast && fast.next){  
        fast = fast.next.next;  
        slow = slow.next;  
        total++;  
    }  
    partial = slow;  
    while(slow){  
        slow = slow.next;  
        total++;  
    }  
    if(total % 2 === 1){  
        back.data = partial.next.data;  
        back.next = partial.next.next;  
        partial.next = null;  
    }  
    else{  
        back.data = partial.data;  
        back.next = partial.next;  
        for(var e=source;e.next!=partial;e=e.next);  
        e.next = null;        
    }  
    front.data = source.data;  
    front.next = source.next;  
}

그러면 연결 목록이 분할되어 분할할 수 없는 단위 노드가 됩니다. 이를 병합하여 새로운 순서 연결 목록으로 조립하는 방법을 찾아야 합니다.

var first = 2 -> 4 -> 6 -> 7 -> null  
var second = 1 -> 3 -> 5 -> 6 -> 8 -> null  
sortedMerge(first, second) === 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 6 -> 7 -> 8 -> null

이러한 메소드를 작성하려면 실제로 고려해야 할 경우가 꽤 많은데, 이는 제 코드에 반영되어 있습니다.

function sortedMerge(l1, l2) {  
    var newList = null;  
    var temp = null;  
    while(l1 && l2){  
        if(l1.data > l2.data){  
            if(!newList){  
                newList = l2;  
                temp = l2;  
            }  
            else{  
                temp.next = l2;  
                temp = l2;  
            }  
            l2 = l2.next;  
        }  
        else{  
            if(!newList){  
                newList = l1;  
                temp = l1;  
            }  
            else{  
                temp.next = l1;  
                temp = l1;  
            }  
            l1 = l1.next;  
        }  
    }  
    if(l1){  
        if(!newList){  
            newList = l1;  
        }  
        else{  
            temp.next = l1;  
        }  
    }  
    if(l2){  
        if(!newList){  
            newList = l2;  
        }  
        else{  
            temp.next = l2;  
        }  
    }  
    return newList;  
}

좋아, 분할 메소드와 병합 메소드는 모두 기록되어 있습니다. , 도마와 식칼이 준비되었듯이 이제 고기를 자르는 일만 남았습니다. 기본 방법 이는 재귀 프로세스입니다.

function mergeSort(list) {  
    if(list && list.next){  
        var front = new Node();  
        var back = new Node();  
        frontBackSplit(list, front, back);  
        return sortedMerge(mergeSort(front),mergeSort(back));  
    }  
    return list;  
}

위는 흥미로운 JavaScript 질문입니다. 링크된 목록의 병합 정렬에 대한 자세한 내용은 PHP 중국어 웹사이트(www.php.cn)를 참고하세요!