목록 정렬

요구사항

head연결리스트의 경우 오름차순 으로 정렬한 후 목록을 반환합니다 .

예시 1:

입력: 헤드 = [4,2,1,3]
출력: [1,2,3,4]
예 2:

입력: 헤드 = [-1,5,3,4,0]
출력: [-1,0,3,4,5]
예시 3:

입력: 헤드 = []
출력: []

풀이방법

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
           if (head == null || head.next == null) {
            return head;
        }

        int length = getLength(head);
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        for (int step = 1; step < length; step *= 2) {
            ListNode prev = dummy;
            ListNode current = dummy.next;

            while (current != null) {
                ListNode left = current;
                ListNode right = split(left, step);
                current = split(right, step);

                prev = merge(left, right, prev);
            }
        }

        return dummy.next;

        
    }
      private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    private ListNode split(ListNode head, int step) {
        if (head == null) {
            return null;
        }

        for (int i = 1; head.next != null && i < step; i++) {
            head = head.next;
        }

        ListNode right = head.next;
        head.next = null;
        return right;
    }

    private ListNode merge(ListNode left, ListNode right, ListNode prev) {
        ListNode current = prev;
        while (left != null && right != null) {
            if (left.val < right.val) {
                current.next = left;
                left = left.next;
            } else {
                current.next = right;
                right = right.next;
            }
            current = current.next;
        }

        current.next = (left != null) ? left : right;
        while (current.next != null) {
            current = current.next;
        }

        return current;
    }
}