LeetCode 148. Sort 리스트 링크 정렬
제목 의 대 의 는 하나의 링크 를 정렬 하고 복잡 도 는 O (nlogn) 안에 있다.사고방식 은 내 가 쓴 것 은 정렬 을 병합 하 는 것 이다. 분 리 된 왼쪽 체인 테이블 의 끝 점 에 있 는 next 치 null 을 주의해 야 한다.
public class SortList {
public ListNode sortList(ListNode head) {
if ( head==null || head.next==null ) return head;
ListNode h1 = head;
ListNode middle = getMiddle(head);
ListNode h2 = middle.next;
middle.next = null;
return mergerList( sortList(h1), sortList(h2) );
}
private ListNode getMiddle(ListNode head ) {
ListNode slow = head;
ListNode fast = head;
while ( fast.next!=null && fast.next.next!=null ) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode mergerList(ListNode h1,ListNode h2) {
ListNode head = new ListNode(-1);
ListNode cur = head;
while ( h1!=null && h2!=null ) {
if ( h1.val<=h2.val ) {
cur.next = h1;
h1 = h1.next;
} else {
cur.next = h2;
h2 = h2.next;
}
cur = cur.next;
}
cur.next = (h1!=null)?h1:h2;
return head.next;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.