Today I Learned

오늘부터 Leetcode에서 코테문제를 꾸준하게 풀어보려고 한다. easy부터 시작해서 문제를 차근차근 풀어보려한다. 영어로 되어있어 백준이나 프로그래머스보단 좀 힘들긴 하지만 재미있었다. 오늘은 풀었던 여러 문제 중 하나를 여기에 정리해보려한다.

21. Merge Two Sorted Lists

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

문제

두 soltedSet을 하나로 합쳐라.

/**
 * 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; }
 * }
 */

풀이과정

• 미리 ListNode라는 클래스를 정의해두고 그걸 기반으로 푸는 문제라서 새롭게 보는 타입이었다.

• Singly-Linked List라서 다음 노드 정보는 있지만 이전 노드 정보는 없었따.

• 우선 두 리스트중 하나가 null이면 자연스럽게 반대 리스트가 반환되게 해두었다.

• while문으로 둘 중 한 리스트가 빌 때 까지 돌린다.

• answer에 빈 노드 하나를 만들고 tmp로 이어 붙인다.

• 한 리스트가 null이 되면 나머지 리스트를 뒤에 이어 붙인다.

• answer의 뒤로 이어붙였으므로, answer.next 즉, 바로 다음 리스트 노드를 반환하면 첫 노드이므로 완료!

Java 코드

class Solution {
  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
      if (list1==null) return list2;
      if (list2==null) return list1;

      ListNode answer = new ListNode();
      ListNode tmp = answer;

      while (list1!=null && list2!=null){
        if (list1.val>list2.val){
          tmp.next = list2;
          list2 = list2.next;
        } else {
          tmp.next = list1;
          list1 = list1.next;
        }
        tmp = tmp.next;
      }
      if (list1==null){
        tmp.next = list2;
      } else {
        tmp.next = list1;
      }
      return answer.next;
  }
}