https://leetcode.com/problems/sort-list/submissions/
난이도 : middle
주어진 단일연결리스트 데이터를 오름차순으로 정렬하는 문제이다.
주어진 시간복잡도는 O(n logn) 이며 공간복잡도는 O(1)이다.
시간복잡도가 O(n logn)이므로 합병정렬을 사용하며 공간복잡도가 1이므로 별도의 배열을 사용하는것은 불가능하다.
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;
}
참고
효팍이의 프로그래밍 -[Leetcode] 리트코드 - 팰린드롬 연결 리스트(Palindrome Linked List) 파이썬(python) 풀이
블로그 참고해주셔서 감사합니당~