Dart에서 두 개의 정렬된 목록 병합 솔루션

두 개의 정렬된 목록 병합

Question

의문

두 개의 정렬된 연결 목록인 list1과 list2의 헤드가 주어집니다. 두 목록을 하나의 정렬된 목록으로 병합합니다. 목록은 처음 두 목록의 노드를 함께 연결하여 만들어야 합니다.
병합된 연결 목록의 헤드를 반환합니다.

예 1:

입력: list1 = [1,2,4], list2 = [1,3,4]
출력: [1,1,2,3,4,4]

예 2:

입력: list1 = [], list2 = []
출력: []

예 3:

입력: list1 = [], list2 = [0]
출력: [0]

제약:

두 목록의 노드 수는 [0, 50] 범위입니다.
-100 <= Node.val <= 100
list1과 list2는 모두 감소하지 않는 순서로 정렬됩니다.

해결책

모든 솔루션은 터미널에서 완벽하게 작동하지만 하나의 솔루션은 두 개의 while 루프 때문에 실행하는 데 더 많은 시간이 걸리지만 모든 테스트를 완료합니다.

질문 섹션에 정의된 솔루션이 아닌 솔루션을 A, B, C, D로 나누었습니다.
솔루션이 많기 때문에 모든 클래스에 동일한 이름을 지정할 수 없으므로 원하는 경우 변경할 수 있는 A, B, C, D로 작성합니다.

노드 클래스

class ListNode {
  int val;
  ListNode? next;
  ListNode([this.val = 0, this.next]);
}

첫 번째 솔루션

class A {
  ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
    if (list1 == null)
      return list2;
    else if (list2 == null) return list1;

    ListNode res = ListNode(-1);
    if (list1.val < list2.val) {
      res.next = list1;
      list1 = list1.next;
    } else {
      res.next = list2;
      list2 = list2.next;
    }
    ListNode? ptr = res.next;
    while (list1 != null && list2 != null) {
      if (list1.val < list2.val) {
        ptr?.next = list1;
        ptr = ptr?.next;
        list1 = list1.next;
      } else {
        ptr?.next = list2;
        ptr = ptr?.next;
        list2 = list2.next;
      }
    }
    while (list1 != null) {
      ptr?.next = list1;
      ptr = ptr?.next;
      list1 = list1.next;
    }
    while (list2 != null) {
      ptr?.next = list2;
      ptr = ptr?.next;
      list2 = list2.next;
    }
    return res.next;
  }

  /*

  Runtime: 361 ms, faster than 100.00% of Dart online submissions for Merge Two Sorted Lists.
  Memory Usage: 143.5 MB, less than 100.00% of Dart online submissions for Merge Two Sorted Lists.

   */
}

두 번째 솔루션

class B {
// 208 / 208 test cases passed, but took too long.

  ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
    List<int>? listMerged = <int>[];

    while (list1 != null) {
      listMerged.add(list1.val);
      list1 = list1.next;
    }

    while (list2 != null) {
      listMerged.add(list2.val);
      list2 = list2.next;
    }

    listMerged.sort();

    ListNode? linkedListMerged = ListNode();
    ListNode head = linkedListMerged;

    for (var i in listMerged) {
      linkedListMerged?.next = ListNode(i);
      linkedListMerged = linkedListMerged?.next;
    }

    return head.next;
  }
}

세 번째 솔루션

약간의 문서

class C {
  // in Node List we have two things one is head which always at
  // the first and tail which always at the end.

  ListNode? head, tail;
  ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
    // checking if the first list value is empty if  it is than we will return the value of the another
    // list and vice versa
    if (list1 == null)
      return list2;
    else if (list2 == null) return list1;

// to store the values of the two lists in another ListNode variable
    ListNode? temp1 = list1;
    ListNode? temp2 = list2;

    // while both are not null  like if we don't enter the null values
    while (temp1 != null && temp2 != null) {
      // and if the first value is larger than the second in a nodeList
      if (temp1.val > temp2.val) {
        // than we will insert the second nodeList value first because
        // as written in the question we also have to arrange the values
        insertNode(temp2.val);
        // than second nodeValue will be our next value
        temp2 = temp2.next;
      } else {
        // if it is  not larger than we will use this condition
        // smaller will will always say at first
        insertNode(temp1.val);
        temp1 = temp1.next;
      }
    }
    // condition if we don't enter the null values
    // than we will set the next value of both nodes into the nodeList
    if (temp1 != null) tail?.next = temp1;
    if (temp2 != null) tail?.next = temp2;
    // return the head
    return head;
  }

  void insertNode(int val) {
    //  than we will insert the node and set it values
    ListNode node = ListNode(val);
    if (head == null)
      head = tail = node;
    else {
      tail?.next = node;
      tail = node;
    }
  }

  /*

  Runtime: 429 ms, faster than 100.00% of Dart online submissions for Merge Two Sorted Lists.
  Memory Usage: 143.8 MB, less than 100.00% of Dart online submissions for Merge Two Sorted Lists.

   */
}

네 번째 솔루션

class D {
  ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
    if (list1 == null) {
      return list2;
    }

    if (list2 == null) {
      return list1;
    }
    ListNode? answer = null;
    if (list1.val > list2.val) {
      answer = list2;
      list2 = list2.next;
    } else {
      answer = list1;
      list1 = list1.next;
    }
    ListNode? current = answer;

    while (list1 != null && list2 != null) {
      if (list1.val > list2.val) {
        current?.next = list2;
        list2 = list2.next;
      } else {
        current?.next = list1;
        list1 = list1.next;
      }
      current = current?.next;
    }

    if (list1 == null) {
      current?.next = list2;
    }
    if (list2 == null) {
      current?.next = list1;
    }

    return answer;
  }

  /*

  Runtime: 443 ms, faster than 100.00% of Dart online submissions for Merge Two Sorted Lists.
  Memory Usage: 143.7 MB, less than 100.00% of Dart online submissions for Merge Two Sorted Lists.
   */
}