[LeetCode] 21. Merge Two Sorted Lists (C#)

LeetCode - Problems - Algorithms - 21. Merge Two Sorted Lists

Problem Description

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.

 

My Solution (C#)

/**
 * 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 l1, ListNode l2) {
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;

        ListNode head = new ListNode();
        ListNode walk = head;
        while (true)
        {
            if (l1.val < l2.val)
            {
                walk.next = l1;
                l1 = l1.next;
            }
            else
            {
                walk.next = l2;
                l2 = l2.next;
            }
            walk = walk.next;

            if (l1 == null)
            {
                walk.next = l2;
                return head.next;
            }
            if (l2 == null)
            {
                walk.next = l1;
                return head.next;
            }
        }
    }
}

얼마전에 python으로도 풀었던 문제라서 풀이는 생략한다...!

라고 생각했는데 안 올렸었나보다~

풀이는 간단하다.

일단 l1이 비어있으면 l2를, l2가 비어있으면 l1을 반환하도록 한다.

 

우리가 작업하는 ListNode는 next와 value 값만 있으므로, 자체적으로 head를 만들어준뒤, walk 즉, 반복문을 통해 같이 따라서 값을 저장하고 연결해줄 walk 값을 만들어준다.

 

나는 중간에 l1이나 l2의 값을 모두 이용하게 되면 return을 이용해 method를 끝마칠 생각이므로 true 값을 확인하는 while 반복문을 열어주었다.

 

이 후 현재 l1과 l2의 값을 비교해 큰 값을 walk.next에 연결해주고, 연결된 값의 다음 값을 불러온다. (e.g. l1 = l1.next;)

 

현재 walk 값의 next값을 walk에 다시 저장한다.

 

만약 l1이나 l2의 값이 null일 경우 비어있지 않은 나머지 node를 walk.next에 연결해준다.

나머지 값은 기존에 연결된 node를 그대로 받아오기 때문에 바로 head.next 값을 리턴해주면 올바른 node list를 반환하게 된다.