LeetCode에서 Merge Two Sorted Lists 풀어보기

문제 링크

bookmark

이번 문제는 list1과 list2라는 두가지의 단일 연결 리스트를 오름차순 형태로 합치는 Merge Two Sorted Lists 의 문제이다.

연결 리스트

• 각 노드들을 포인터로 연결한 자료구조
• 탐색은 O(n)이 소요되며, 추가와 제거는 O(1)이 소요됨
• 때문에 추가와 삭제가 반복되는 로직이라면 배열말고 연결리스트가 유리함
• 단일 연결리스트, 이중 연결리스트, 선형 연결리스트 형태가 존재함

소스코드

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    
    let newNodeList = new ListNode(0);
    const result = newNodeList;
    
    while(list1 !== null && list2 !== null) {
        if(list1.val < list2.val) {
            newNodeList.next = list1;
            list1 = list1.next;
        }
        else {
            newNodeList.next = list2;
            list2 = list2.next;
        }
        newNodeList = newNodeList.next;
    }
    
			if(list1 !== null) newNodeList.next = list1;
	    if(list2 !== null) newNodeList.next = list2;

    return result.next
};

1. 제공된 연결리스트 생성자로 하나의 연결리스틀 만들어준다.
2. return 할 result의 변수에 참조를 해준다
3. list1의 노드값과 list2의 노드값을 계속 비교해줄 while문을 만들어준다
4. list1의 노드값이 더 작으면 list1을 새로 만들어준 연결 리스트인 newNodeList에 next를 사용하여 포인터로 연결해준다.
5. 그 반대인 경우는 list2를 넣어준다
6. newNodeList 의 꼬리 부분을 갱신해준다
7. list1과 list2에서 둘중 하나라도 null 값이 나오면 반복문을 종료한다
8. 만약 남아 있는 연결리스트에서 null 값이 아닌 리스트가 있다면 그 리스트의 나머지 노드를 포인터로 연결해준다.
9. result.next를 사용하여 연결된 노드들을 return 해준다