js에서 두 개의 연결된 목록의 첫 번째 공통 노드를 찾는 알고리즘

이 글은 js에서 두 연결 리스트의 첫 번째 공통 노드를 찾는 알고리즘을 공유합니다. 필요한 참조 값이 있습니다.

문제 설명

두 개의 연결 리스트를 입력하고 첫 번째 공통 노드를 찾습니다.

Analytic

두 연결리스트의 길이가 동일하지 않다는 점을 고려하여 두 연결리스트의 길이 차이를 계산한 후 긴 연결리스트가 먼저 길이를 완성해야 합니다. 차이가 있고 두 개의 연결된 목록이 연결된 목록이고 함께 이동합니다.

코드 구현

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(h1, h2)
{
    var h1Len = 0, h2Len = 0;
    var cur = h1;
    
    while(cur!==null){
        h1Len++;
        cur = cur.next;
    }
    
    cur = h2;
    while(cur!==null){
        h2Len++;
        cur = cur.next;
    }
    
    var distance = 0;
    var t1, t2;
    if(h1Len > h2Len){
        t1 = h1;
        t2 = h2;
        distance = h1Len - h2Len;
    }else{
        t1 = h2;
        t2 = h1;
        distance = h2Len - h1Len;
    }
    
    while(distance !== 0){
        t1 = t1.next;
        distance--;
    }
    
    while(t1 !== t2){
        t1 = t1.next;
        t2 = t2.next;
    }
    
    return t1;
}

관련 권장사항:

js에서 슬라이딩 윈도우의 최대값을 구현하는 알고리즘​​ #🎜 🎜#

두 개의 스택을 사용하여 js에서 대기열 알고리즘 구현

위 내용은 js에서 두 개의 연결된 목록의 첫 번째 공통 노드를 찾는 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!