문제

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

제한사항

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both l1 and l2 are sorted in non-decreasing order.

접근

알고리즘에 대해 공부해보신 분이라면 병합 정렬Merge Sort의 merge 기능을 링크드 리스트로 구현하는 문제라는 것을 알 수 있습니다(블로그 참고 해주세요...ㅎㅎ). 바로 답안 들어가겠습니다!

답안

/**
 * Definition for singly-linked list.
 * 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 class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(null == l1 && null == l2)
            return null;

        ListNode retNode = new ListNode();
        ListNode node = retNode;
        while(null != l1 && null != l2){
            if(l1.val <= l2.val){
                retNode.val = l1.val;
                l1 = l1.next;
            }else{
                retNode.val = l2.val;
                l2 = l2.next;
            }

            retNode.next = new ListNode();
            retNode = retNode.next;
        }
        while(null != l1){
            retNode.val = l1.val;
            l1 = l1.next;

            if(null == l1)
                break;

            retNode.next = new ListNode();
            retNode = retNode.next;
        }
        while(null != l2){
            retNode.val = l2.val;
            l2 = l2.next;

            if(null == l2)
                break;

            retNode.next = new ListNode();
            retNode = retNode.next;
        }
        return node;
    }
}