[LeetCode/JAVA] 21. Merge Two Sorted Lists

https://github.com/ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

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

Merge Two Sorted Lists - LeetCode

문제 설명

출처 : LeetCode

주어진 두 개의 노드 리스트를 병합하여 정렬된  노드 리스트를 반환하세요.

풀이 방법

LinkedList에 담은 후 값으로 정렬시킨 뒤 정렬된 값으로 return ListNode를 생성하였습니다.

1. LinkedList에 주어진 ListNode의 노드들을 모두 삽입합니다.
2. 노드들의 값을 기준으로 LinkedList를 정렬합니다.
3. 정렬된 LinkedList로 return 객체를 생성합니다.

내 코드(JAVA)

 

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    LinkedList<ListNode> linkedList = new LinkedList<>();

    // LinkedList에 각각의 Node를 담기
    while(l1 != null) {
        linkedList.add(l1);
        l1 = l1.next;
    }

    while(l2 != null) {
        linkedList.add(l2);
        l2 = l2.next;
    }

    // 값을 기준으로 정렬
    linkedList.sort(new Comparator<ListNode>() {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            if(o1.val > o2.val) return 1;
            else if(o1.val < o2.val) return -1;
            return 0;
        }
    });

    // return 객체 생성
    ListNode tempNode = new ListNode();
    ListNode res = tempNode;

    for(ListNode node : linkedList) {
        tempNode.next = node;
        tempNode = tempNode.next;
    }

    return res.next;
}

다른 사람 코드

 

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(0);
    ListNode handler = head;
    while(l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            handler.next = l1;
            l1 = l1.next;
        } else {
            handler.next = l2;
            l2 = l2.next;
    	}
    	handler = handler.next;
    }

    if (l1 != null) {
    	handler.next = l1;
    } else if (l2 != null) {
    	handler.next = l2;
    }

    return head.next;
}

 

주어진 2개의 ListNode는 정렬되어있으므로 각 ListNode의 첫 번째 Node부터 비교하여 차곡차곡 쌓는 방식

마지막에 남는 노드는 따로 처리해주었네요.

 

제 방법은 너무 1차원적으로 푼 것 같습니다. 조금 더 연습한 뒤 이 문제는 추후 다시 한번 풀어보겠습니다.