【LeetCode】Sort List解題レポート(チェーンテーブルの集計ソート)
2176 ワード
【テーマ】
Sort a linked list in O(n log n) time using constant space complexity.
【集計ソート】
この問題は意外にもACを1回やったが、考えてみれば、基礎的なアルゴリズムで、これは集計ソートとチェーンテーブルの基本的な操作に熟練していることを説明するしかない.
Sort a linked list in O(n log n) time using constant space complexity.
【集計ソート】
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null) return null;
// only one node
if (head.next == null) return head;
// only two nodes
if (head.next.next == null) {
if (head.val <= head.next.val) {
return head;
} else {
ListNode newhead = head.next;
head.next.next = head;
head.next = null;
return newhead;
}
}
// more than three nodes
// divide the list two parts
ListNode f = head, s = head;
while (f != null && f.next != null) {
f = f.next.next;
s = s.next;
}
ListNode m = s.next;
s.next = null; // make the first part end
// sort the two parts individually
ListNode n1 = sortList(head);
ListNode n2 = sortList(m);
// find the new head afther merge
ListNode newhead;
if (n1.val <= n2.val) {
newhead = n1;
n1 = n1.next;
} else {
newhead = n2;
n2 = n2.next;
}
// merge the two sorted parts
ListNode n3 = newhead;
while (n1 != null && n2 != null) {
if (n1.val <= n2.val) {
n3.next = n1;
n3 = n3.next;
n1 = n1.next;
} else {
n3.next = n2;
n3 = n3.next;
n2 = n2.next;
}
}
if (n1 != null) {
n3.next = n1;
}
if (n2 != null ) {
n3.next = n2;
}
return newhead;
}
}
この問題は意外にもACを1回やったが、考えてみれば、基礎的なアルゴリズムで、これは集計ソートとチェーンテーブルの基本的な操作に熟練していることを説明するしかない.