[LeetCode] 148. Sort List

https://leetcode.com/problems/sort-list/description/?envType=study-plan-v2&envId=top-interview-150 

Sort List - LeetCode

링크드 리스트의 헤드가 주어지면 오름차순으로 정렬한 후 목록을 반환합니다.

 

히든미션 : O(n logn) 시간과 O(1) 메모리(즉, 상수 공간)에서 정렬

 

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

문제접근

히든미션을 성공하기위해 병합정렬 또는 퀵정렬을 사용해보려고 하였지만,

링크드 리스트의 길이를 파악하는것이 까다로워서 일단 쉽게 구현해 보았습니다.

 

1. 주어진 리스트의 원소들을 꺼내 ArrayList에 넣습니다.

2. ArrayList를 정렬합니다.

3. 정렬된 ArrayList의 원소들을 다시 Linked List로 만들어 반환합니다.

 

    public ListNode sortList (ListNode head){
        ArrayList<Integer> temp = new ArrayList<>();
        if (head == null) {
            return head;
        }
        while (head.next != null) {
            temp.add(head.val);
            head = head.next;
        }
        temp.add(head.val);

        Collections.sort(temp);

        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        for (var value : temp) {
            tail.next = new ListNode(value);
            tail = tail.next;
        }

        return dummy.next;
    }

 

시간복잡도

최대 주어지는 head의 연결된 ListNode만큼 반복됩니다.

시간복잡도는 O(n)입니다.

 

다른사람의 코드

병합정렬로 구현을 실패했기에 병합정렬이 구현된 코드를 참고하였습니다.

 

Linked List를 절반으로 나누기 위해 low Fast 방법을 사용합니다.

Fast는 2칸씩 Slow는 1칸씩 Linked List를 탐색합니다.

Fast가 null을 만나게되면 Slow의 위치가 길이의 절반이 되는 것입니다.

 

위 방법으로 병합정렬을 합니다.

public ListNode sortList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode slow=head;
        ListNode fast=head;
        ListNode prev=null;

        while(fast!=null && fast.next!=null){
            prev=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        prev.next=null;
        ListNode l1=sortList(head);
        ListNode l2=sortList(slow);
        //System.out.println(l1.val);
        return mergeSort(l1,l2);
    }
    public static ListNode mergeSort(ListNode l1,ListNode l2){
        ListNode fh=null;
        ListNode ft=null;

        while(l1!=null && l2!=null){
            if(fh==null && ft==null){
                if(l1.val>l2.val){
                    fh=l2;
                    ft=l2;
                    l2=l2.next;
                }
                else{
                    fh=l1;
                    ft=l1;
                    l1=l1.next;
                }
            }
            if(l1!=null && l2!=null){
                if(l1.val<l2.val){
                    ft.next=l1;
                    ft=ft.next;
                    l1=l1.next;
                }
                else{
                    ft.next=l2;
                    ft=ft.next;
                    l2=l2.next;
                }
            }
        }
        if(l1!=null){
            ft.next=l1;
        }
        if(l2!=null){
            ft.next=l2;
        }
        return fh;
    }

 

느낀점

아직 병합정렬을 마음대로 구현하기는 조금 부족한것 같습니다.

위 문제를 더 연습해서 병합정렬에 대해 더 공부하도록 하겠습니다.

 

참고

💯✅JAVA | USING MERGE SORT ALGORITHM - Sort List - LeetCode