LeetCode 148. Sort 리스트 링크 정렬

일정한 공간 복잡성 을 사용 하여 O (n log n) 시간 에 연 결 된 목록 을 정렬 합 니 다. 제목 링크
제목 의 대 의 는 하나의 링크 를 정렬 하고 복잡 도 는 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;
    }
}

좋은 웹페이지 즐겨찾기