[Merge Two Sorted Lists]

출처:https://leetcode.com/problems/merge-two-sorted-lists/description/

 

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

 

당신에게 두 개의 정렬된 연결 리스트 list1과 list2의 시작점(머리)가 주어집니다.
두 리스트를 하나의 정렬된 리스트로 병합하세요. 이 리스트는 처음 두 리스트의 노드들을 함께 연결해서 만들어야 합니다.
병합된 연결 리스트의 시작점(머리)을 반환하세요.

1.두 리스트의 현재 노드를 가리키는 포인터를 생성합니다. 
2.두 포인터가 가리키는, 노드의 값을 비교합니다.
3.값이 더 작은 노드를 결과 리스트에 추가합니다.
4.사용된 노드의 포인터를 다음 노드로 이동합니다.
5.두 리스트 중 하나가 모두 소진될 때까지 2-4 단계를 반복합니다.
6.남은 리스트의 나머지 부분을 결과 리스트에 붙입니다.

 

수도코드

function mergeTwoLists(ListNode list1, ListNode list2) {
    // 더미 노드 생성
    ListNode dummy = new ListNode(-1);
    ListNode current = dummy;
    
    // 두 리스트를 모두 순회하면서 병합
    while (list1 != null && list2 != null) {
        // 더 작은 값을 가진 노드를 결과 리스트에 추가
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    
    // 남은 노드 처리
    if (list1 != null) {
        current.next = list1;
    } else {
        current.next = list2;
    }
    
    // 결과 리스트의 헤드 반환
    return dummy.next;
}

 

/**
 * ListNode 클래스 정의 수도코드
 */
public class ListNode {
    int val;
    ListNode next;
    
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

/**
 * 두 정렬된 연결 리스트를 병합하는 메소드
 */ 
 public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 더미 헤드 노드를 생성하여 결과 리스트의 시작점을 쉽게 관리
        ListNode dummy = new ListNode(-1);
        // 현재 위치를 추적하는 포인터 설정
        ListNode current = dummy;
        
        // 두 리스트 모두 노드가 남아있는 동안 반복
        while (list1 != null && list2 != null) {
            // list1의 현재 값이 더 작거나 같으면
            if (list1.val <= list2.val) {
                // list1의 현재 노드를 결과 리스트에 추가
                current.next = list1;
                // list1 포인터를 다음 노드로 이동
                list1 = list1.next;
            } else {
                // list2의 현재 값이 더 작으면 list2의 노드를 결과 리스트에 추가
                current.next = list2;
                // list2 포인터를 다음 노드로 이동
                list2 = list2.next;
            }
            // 현재 포인터를 방금 추가한 노드로 이동
            current = current.next;
        }
        
        // 한쪽 리스트가 모두 소진되면 남은 다른 리스트를 그대로 연결
        // list1이 남아있으면 list1의 나머지를 연결
        if (list1 != null) {
            current.next = list1;
        } else {
            // list2가 남아있거나 둘 다 비어있으면 list2를 연결
            current.next = list2;
        }
        
        // 결과 리스트의 실제 시작점(더미 노드 다음)을 반환
        return dummy.next;
    }
}