[Divide & Conquer] Sort List

148. Sort List

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

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

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 
 * Runtime	: 152 ms
 * Memory	: 70.31 MB
 */
var sortList = function(head) {
  const vals = [];  
  let cur = head;

  while(cur) {
    vals.push(cur.val);
    cur = cur.next
  }

  vals.sort((a, b) => b - a);

  cur = new ListNode(0);
  const ans = cur;

  while(vals.length) {
    cur.next = new ListNode(vals.pop());
    cur = cur.next;
  }

  return ans.next;
};

주제[Divide & Conquer]에 적절한 해답은 아니었습니다.

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

2-1. Using divide & conquer

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

/*
 * Runtime	: 149 ms
 * Memory	: 68.26 MB
 */
var sortList = function(head) {
  if (!head || !head.next) return head;

  let mid = getMid(head);
  let rightSide = sortList(head);
  let leftSide = sortList(mid);
  
  return merge(rightSide, leftSide);
};

var getMid = function(head) {
  let slow = head;
  let fast = head.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let mid = slow.next;
  slow.next = null;
  return mid;
}

var merge = function(right, left) {
  let dummy = new ListNode(0);
  let curr = dummy;

  while (right && left) {
    if (right.val < left.val) {
      curr.next = right;
      right = right.next;
    } else {
      curr.next = left;
      left = left.next;
    }
    curr = curr.next;
  }
  
  // if any linked list is not traversed thoroughly
  curr.next = right ? right : left;
  return dummy.next;
}

필자의 해답과 달리 주제[Divide & Conquer]에 적절한 해답입니다. 단, 시간복잡도O(n log n)는 동일하며, 공간복잡도 O(n) → O(n log n)의 성능은 낮아졌습니다.

1 해답 시간복잡도 요인: sort 메소드
2 해답 시간복잡도 요인: sortList 함수(log n) x merge 함수(n)