LeetCode - merge two sorted lists

katanazero86·2020년 6월 8일
0

leetcode

목록 보기
13/13
post-thumbnail

merge two sorted lists

  • Difficulty : easy

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

  • linked list 2개가 주어지면 이걸 값을 기준으로 정렬해서 하나의 linked list 로 반환을 하면 된다.

example
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

solution

  • 작성 언어 : javascript
  • Runtime : 80ms
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {

  if (l1 == null && l2 == null) {
    return null;
  }

  const tempArray = [];
  const mergeListNode = new ListNode(0, null);

  const readListNode = function read(targetListNode) {
    if (targetListNode.val != undefined) {
      tempArray.push(targetListNode.val);
    } else {
      tempArray.push(0);
    }

    if (targetListNode.next != null) {
      read(targetListNode.next);
    }
  }

  if (l1 != null) {
    readListNode(l1);
  }

  if (l2 != null) {
    readListNode(l2);
  }


  tempArray.sort((a, b) => {

    if (a > b) {
      return 1;
    }

    if (a < b) {
      return -1;
    }

    return 0;
  });

  let recursiveCount = tempArray.length;
  const createListNode = function create(targetListNode, index) {

    if (recursiveCount === 0) {
      return false;
    }

    targetListNode.val = tempArray[index];

    if (recursiveCount === 1) {
      targetListNode.next = null;
    } else {
      targetListNode.next = new ListNode(0, null);
    }

    recursiveCount--;
    return create(targetListNode.next, index + 1);
  }

  createListNode(mergeListNode, 0);

  return mergeListNode;

};

function ListNode(val, next) {
  this.val = val;
  this.next = next;
}
  • 재귀함수로 해결을 하였다. 병합할 linked list 를 순회하면서 값만 추출하여 배열에 저장한 후, 이걸 오름차순 정렬하였다.
  • 정렬된 배열에 길이가 생성해야할 linked list 숫자이므로 몇번 기저조건 변수로 사용하여 재귀적으로 linked list 를 생성하도록 함.
profile
developer life started : 2016.06.07 ~ 흔한 Front-end 개발자(현재는 백수 얏호👻)

0개의 댓글