Hackerrank - Merge two sorted linked list

https://www.hackerrank.com/challenges/one-week-preparation-kit-merge-two-sorted-linked-lists/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=preparation-kits&playlist_slugs%5B%5D=one-week-preparation-kit&playlist_slugs%5B%5D=one-week-day-five 

Merge two sorted linked lists | HackerRank

최근에 hackerrank에서 일주일 interview  문제를 풀고 있는데, 고칠점이 있어서 작성한다.

 

 

function mergeLists(head1, head2) {
    let head = null
    let cur = head;
    while(head1&&head2){
        if(head1.data<head2.data){
            if(head==null){
                head = new SinglyLinkedListNode(head1.data,null);   
                cur =head; 
            }else{
                let node = new SinglyLinkedListNode(head1.data,null);
                cur.next= node;
                cur = cur.next;
            }
            head1=head1.next;     
        }else{
            if(head==null){
                head = new SinglyLinkedListNode(head2.data,null); 
                cur =head;    
            }else{
                let node = new SinglyLinkedListNode(head2.data,null);
                cur.next= node;
                cur= cur.next;
            }
            head2=head2.next; 
        }
    }
    while(head1){
        if(head==null){
                head = new SinglyLinkedListNode(head1.data,null);   
                cur =head; 
            }else{
                let node = new SinglyLinkedListNode(head1.data,null);
                cur.next= node;
                cur = cur.next;
            }
            head1=head1.next;   
    }
    while(head2){
        if(head==null){
                head = new SinglyLinkedListNode(head2.data,null); 
                cur =head;    
            }else{
                let node = new SinglyLinkedListNode(head2.data,null);
                cur.next= node;
                cur= cur.next;
            }
            head2=head2.next; 
    }
    return head;
}

두 정렬된 링크드 리스트를 머지하는 문제다.

 

내가 생각한 코드는 이렇다.

 

1. A,B가 둘다 null이 아니면 head1,head2를 비교함

2. 더 작은 리스트의 첫 값을 head에 넣어줌

3. 링크드 리스트 이동 후 반복

4. A,B 둘 중 하나가 null이면 이후 남은 링크드리스트의 값을 넣어줌

 

머지소트를 할떄와 로직은 동일했는데, 더 좋은 코드가 있었다.

 

function mergeLists(headA, headB) {
    if (!headA) return headB;
    if (!headB) return headA;
    
    var nodeA = headA;
    var nodeB = headB;
    
    var head = new SinglyLinkedListNode(null);
    var leader = head;
    while(nodeA || nodeB){
        // Handle reaching the end of either list.
        if (!nodeA){
            leader.next = nodeB;
            break;
        }
        if (!nodeB){
            leader.next = nodeA;
            break;
        }
        
        // Select the next lowest node.
        if(nodeA.data < nodeB.data){
            leader.next = nodeA;
            nodeA = nodeA.next;
        }
        else {
            leader.next = nodeB;
            nodeB = nodeB.next;
        }
        leader = leader.next;
    }
    
    return head.next;
}

링크드리스트의 특성을 통해 만약 둘 중 하나가 null이라면

나머지 링크드 리스트의 첫 값을 리스트의 next로 넣어주면 알아서 나머지 애들도 따라오는 것이다!

 

그리고 리턴할 링크드 리스트의 포인터에도 값이 있어야하기 떄문에 head가 null일때/ 아닐떄를 구분해주었는데,

 

이것보다 위의 코드처럼 head.next로 그냥 다음 노드 주소값을 넘겨주는편이 훨씬 더 간단하다.

 

배울점이 많은 코드다.