<Easy> Merge Two Sorted Lists (LeetCode : C#)

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

📕 문제 설명

두 정렬된 연결 리스트의 head가 주어질 때 합친 후 하나의 정렬된 list의 head 반환하기

• Input
  두 정렬된 연결 리스트 head
• Output
  병합된 하나의 연결리스트 head

예제

1. 풀이

1. 각 리스트의 값들 한 리스트에 합치기
2. 리스트 정렬
3. 새 연결 리스트 만든 후 head 반환

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode list1, ListNode list2) {

        List<int> mergedList = new List<int>();
        while (list1 != null)
        {
            mergedList.Add(list1.val);
            list1 = list1.next;
        }

        while (list2 != null)
        {
            mergedList.Add(list2.val);
            list2 = list2.next;
        }

        mergedList.Sort();
        ListNode currNode = new ListNode(0);
        ListNode answerNode = currNode;

        foreach(int value in mergedList)
        {
            currNode.next = new ListNode(value);
            currNode = currNode.next;
        }

        return answerNode.next;
        
    }
}

1. 결과

2. 풀이

굳이 다 담고 정렬 말고 한번에 쭉 보는 방법

1. 각 리스트의 값 보면서 더 작은 애를 하나씩 붙여나간다.
2. 만약 둘 중 하나가 null이 되면 남은 것의 list를 뒤에 붙인다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode list1, ListNode list2) {

        ListNode currNode = new ListNode(0);
        ListNode answerNode = currNode;

        while (list1 != null && list2 != null)
        {
            if (list1.val < list2.val)
            {
                currNode.next = new ListNode(list1.val);
                list1 = list1.next;
            }
            else
            {
                currNode.next = new ListNode(list2.val);
                list2 = list2.next;
            }
            currNode =  currNode.next;
        }

        if (list1 != null)
        {
            currNode.next = list1;
        }

        if (list2 != null)
        {
            currNode.next = list2;
        }

        return answerNode.next;
        
    }
}

2. 결과