[LeetCode] 148. Sor List

yeong·2022년 5월 27일

알고리즘

목록 보기

4/5

문제:

https://leetcode.com/problems/sort-list/submissions/
난이도 : middle

문제 접근 :

주어진 단일연결리스트 데이터를 오름차순으로 정렬하는 문제이다.
주어진 시간복잡도는 O(n logn) 이며 공간복잡도는 O(1)이다.
시간복잡도가 O(n logn)이므로 합병정렬을 사용하며 공간복잡도가 1이므로 별도의 배열을 사용하는것은 불가능하다.

문제 풀이

우선 데이터를 작은 단위로 쪼개도록, 리스트를 분할하는 partition함수를 생성한다.
다른 로직은 일반 배열문제와 비슷했으나, 연결리스트의 분할하는데 어려움을 겪었다. 한참을 헤매다 다른사람의 작성코드를 참고하였는데, 연결리스트의 중간값을 구하는데 "런너기법"이라는 것을 사용한다고한다.
이를 활용하여 연결리스트를 분할하여 반환하는 함수를 생성한다.

function partition(node) {
  let slow = node;
  let fast = node;

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  const left = node;
  const right = slow.next;
  slow.next = null;
  return [left, right];
}

partition 함수를 활용하여 분할을 반복하는 재귀함수를 생성한다. 더 이상 쪼갤 수 없는 상태, 즉 node 또는 node.next가 null이라면 node를 이미 정렬된 상태와 같으므로 바로 반환한다.
이렇게 최대한쪼개어 모두 정렬된 상태로 반든 리스트를 다시 병합한다.
병합을 위해서 별도로 병합함수를 생성하도록한다.
병합함수 merge는 두개의 node를 받아, 각각의 val을 비교하고 순차적으로 별도의 임시 리스트에 담는다. 일반 합병정렬의 처리와 유사하다.
최종적으로 순차적으로 정렬된 하나의 node를 반환한다.


function merge(nodeA, nodeB) {
  let head = new ListNode();
  let node = head;
  while (nodeA !== null && nodeB !== null) {
    if (nodeA.val < nodeB.val) {
      node.next = nodeA;
      nodeA = nodeA.next;
    } else {
      node.next = nodeB;
      nodeB = nodeB.next;
    }
    node = node.next;
  }

  while (nodeB !== null) {
    node.next = nodeB;
    nodeB = nodeB.next;
    node = node.next;
  }

  while (nodeA !== null) {
    node.next = nodeA;
    nodeA = nodeA.next;
    node = node.next;
  }

  return head.next;
}

분할된 리스트를 merge함수를 이용해 순차적으로 병합한다.
모두 정렬된 리스트를 반환한다.

최종 코드

var sortList = function(head) {
    
   function DFS(node) {
    if (node === null || node.next === null) {
      return node;
    } else {
      let [nodeA, nodeB] = partition(node);
      return merge(DFS(nodeA), DFS(nodeB));
    }
  }
    let answer= DFS(head);
    return answer;
}

function partition(node) {
  let slow = node;
  let fast = node;

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  const left = node;
  const right = slow.next;
  slow.next = null;
  return [left, right];
}


function merge(nodeA, nodeB) {
  let head = new ListNode();
  let node = head;
  while (nodeA !== null && nodeB !== null) {
    if (nodeA.val < nodeB.val) {
      node.next = nodeA;
      nodeA = nodeA.next;
    } else {
      node.next = nodeB;
      nodeB = nodeB.next;
    }
    node = node.next;
  }

  while (nodeB !== null) {
    node.next = nodeB;
    nodeB = nodeB.next;
    node = node.next;
  }

  while (nodeA !== null) {
    node.next = nodeA;
    nodeA = nodeA.next;
    node = node.next;
  }

  return head.next;
}

정리

"런너기법" 에 대해 아직 정리가 안된부분이 많아 정리가 필요하다. (홀수,짝수 차이 )
연결리스트의 링크상태에 대해 종종 실수가 있다. node가 바로 할당되었다면, 같은 참조값을 갖고있으며 재할당된경우 해당 변수는 참조값을 잃어버리지만 다른 변수에서는 여전히 유지됨을 기억하자.

참고
효팍이의 프로그래밍 -[Leetcode] 리트코드 - 팰린드롬 연결 리스트(Palindrome Linked List) 파이썬(python) 풀이