[Linked List] Merge Two Sorted Lists

21. Merge Two Sorted Lists

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 
 * Runtime	: 70 ms
 * Memory	: 44.10 MB
 */
var mergeTwoLists = function(list1, list2) {
  let listAnsCur = new ListNode(0);
  const listAns = listAnsCur;

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

    listAnsCur = listAnsCur.next;
  }

  while(list1) {
    listAnsCur.next = new ListNode(list1.val);
    list1 = list1.next;
    listAnsCur = listAnsCur.next;
  }

  while(list2) {
    listAnsCur.next = new ListNode(list2.val);
    list2 = list2.next;
    listAnsCur = listAnsCur.next;
  }

  return listAns.next;
};

JS의 optional chaining을 활용해 while문을 줄이고 싶었습니다.

...
  while(list1 || list2) {
    if(list1?.val <= list2?.val){
      listAnsCur.next = new ListNode(list1?.val);
      list1 = list1?.next;
    }else {
      listAnsCur.next = new ListNode(list2?.val);
      list2 = list2?.next;
    }

    listAnsCur = listAnsCur.next;
  }

하지만 다음과 같은 에러가 발생하여,

Runtime Error
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Last Executed Input [1], []

본 해답과 같이 여러 while문을 사용해 세분화하였습니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using recursion

해답의 전문은 링크를 확인해주세요.

/*
 * Runtime	: 67 ms
 * Memory	: 44.67 MB
 */
var mergeTwoLists = function (l1, l2) {
  if (!l1) return l2;
  else if (!l2) return l1;
  else if (l1.val <= l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2
  }
};

직전 문제 [Linked List] Add Two Numbers와 같이 재귀를 사용한 해답입니다. 필자의 해답과 비교하여 가독성이 높아졌습니다.